Paxos: Accepting Proposals With Different Values and Consensus in Paxos
Question 1: This means that an acceptor can accept a proposal with a value $v_2$ after it has accepted a proposal with value $v_1$. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?


Yes, it is possible for an acceptor to accept a proposal with number $n_2$ and value $v_2$ after it has accepted a proposal with number $n_1$ and value $v_1$. Consider the following scenario where there are two proposers $p_1$ and $p_2$ and three acceptors $a_1, a_2,$ and $a_3$: 


$p_1$ proposes $\texttt{propose}(n_1,*)$ to $a_1$ and $a_2$.
both $a_1$ and $a_2$ respond to $p_1$ with (a) a promise never again to accept a proposal numbered less than $n_1$ and (b) no proposal because they have not accepted any ones.
$p_1$ receives the two responses from $a_1$ and $a_2$. Now $p_1$ is free to select its own value $v_1$. $p_1$ sends $\texttt{accept}(n_1, v_1)$ to $a_1$ and $a_2$.
$a_1$ accepts $(n_1, v_1)$ but $a_2$ does not (maybe this message to it has been lost; note that an acceptor can ignore any request without compromising safety).
$p_2$ proposes $\texttt{propose}(n_2, *)$ to $a_2$ and $a_3$ ($n_2 &gt; n_1$).
Because, in 4, $a_2$ does not accept $\texttt{accept}(n_1,v_1)$ from $p_1$, both $a_2$ and $a_3$ respond to $p_2$ with a promise never again to accept a proposal numbered less than $n_2$.
$p_2$ receives the two responses from $a_2$ and $a_3$ and is also free to select its own value $v_2$. $p_2$ sends $\texttt{accept}(n_2, v_2)$ to $a_1$ and $a_3$.
$a_1$ can now accept the proposal $(n_2, v_2)$ from $p_2$.





  Question 2: (1) Does this mean that if a proposer proposes a value, $v_1$, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, $v_2$? (2) If they want to make a proposal, they must propose the same value, $v_1$? (3) The only way they could propose a different value would be to start a new instance of Paxos. (4) The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?


For (1): yes; For (2), yes. The invariant $\texttt{P2B}$ in Paxos is the key to its correctness. 

For (3): I think you have confused an instance of Paxos with a round in an instance of Paxos. They are two important concepts. We call a round the collection of all messages labeled with some particular proposal $n$. An instance of Paxos consists of multiple rounds, each round corresponding to a proposal with a different number. If you consider multiple instances of Paxos, please refer to Section 3 "Implementing a State Machine" in the paper. It is often called "multi-Paxos".

For (4): in page 6, it reads "A proposer can make multiple proposals, so long as it follows the algorithm for each one. It can abandon a proposal in the middle of the protocol at any time". That is to say, as a proposer, you are free to make multiple proposals as you want, for no matter what reasons. However, a major reason would be to learn the value already chosen: at phase 2(a), you will have to select the value chosen, if any.




  Question 3: Can an acceptor respond to a proposer with a promise if consensus has already been reached?


Yes, it does no harm. Again, the invariant $\texttt{P2B}$ works.




  Question 4: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send a proposal, correct?


Are you discussing about the correctness of Paxos? Are you regarding the "promise mechanism" as the key to success? If so, you are almost right: however, it is hard to identify a single factor in Paxos. If it must be done, once again, it is the $\texttt{P2B}$ invariant.