CSE 452: Distributed Systems

Problem Set 4: MultiPaxos

Due: Tuesday, November 14, 11:59pm via Gradescope

The problems below are about the version of the MultiPaxos protocol presented in lecture.

  • Imagine we have an infinite number of copies of single-decree Paxos indexed by a slot number, which is a positive integer.
  • All nodes play all roles.
  • We combine ballot numbers across all slots.
  • A ballot is a combination of a per-node sequence number and the node's name.
  • We combine phase 1 across all slots. 1b messages contain of vote summaries for all nonempty slots.
  • We define a node to be the leader for ballot \(b\) if it has collected a majority of 1b message in \(b\).
  • Clients broadcast requests to the all servers. Leaders place client requests into the first available slot and try to get them chosen.
  • When a leader is elected, it proposes no-ops in all empty slots that have slot number less than any non-empty slot.
  • We assume 2a/2b messages are sent separately for each slot, so these messages have a slot number on them in addition to single-decree Paxos data. (You can batch these messages in lab 3 if you want, but we ignore that here.)
  • For all problems except problem 10, we ignore heartbeats and garbage collection.

This protocol is less well specified than Single-Decree Paxos, so you will necessarily need to keep your explanations high-level. Your answers should make sense to anyone who has studied the lectures from this class—you should not depend on details of your own lab 3 design.

In our discussion below, we imagine that sending a message adds it to the set of messages in the network, but receiving a message does not remove it from the set. In other words, once a message is sent, it is "in the network" forever.

We define \(\mathit{Chosen}(i, v)\) where \(i\) is a slot number and \(v\) is a value to mean that there exists a ballot \(b\) and a set of nodes \(S\) such that the size of \(S\) is greater than \(\lfloor n/2\rfloor\) and every node in \(S\) has sent an AcceptResponse (2b) message with contents \((i, b, v)\).

To "describe a execution", list the events that happen. An event could be a message delivery or "spontaneous action" or timer firing, or it could be a network failure (drop, duplicate, delay, reorder) or node failure. No need to explain the events, just list them. Also, if there are a lot of events, you can describe them at a high level instead of listing them one by one, but be sure that your reader can understand what specific execution you are talking about.

For all problems assume there are \(n=3\) nodes, \(N_1\), \(N_2\), and \(N_3\) and that \(N_1 < N_2 < N_3\) in the ballot ordering.

Each problem is worth 10 points.

What goes weird but right

  1. Describe a execution where two different nodes think they are currently the leader.

    Hint: They will be leaders of different ballots.

  2. In the scenario from the previous problem, explain why MultiPaxos does not violate linearizability even though there are multiple leaders.

    Hint: The leaders are leaders of different ballots.

  3. Describe a execution where a value is chosen for slot 1 but no node knows that it is chosen yet.

  4. Describe a execution where a value has been chosen for slot 2 but no value is chosen (yet) in slot 1.

  5. Describe a execution where one client's requested value is chosen in two different slots (i.e., the same value is chosen in two different slots).

    Edit: This question was originally unclear about whether leaders attempted deduplication. I should have included the following discussion, but it is also fine if you answer the question without considering leader deduplication.

    (Here' what I should have included in the question.) Suppose that leaders attempt to deduplicate client requests as follows. When a leader receives a request, it first looks in its log to see if that request is already in the log, and if so, it ignores the request. Otherwise, it puts the request into the first available slot.

What would go wrong

  1. Using only finite message delays and reordering (and not node failures, message drops or duplicates) describe an infinite execution where no value is ever chosen even though clients are submitting requests.

  2. Suppose the leader did not propose no-ops for empty slots when it got elected. Describe a situation where the system would stop executing client requests. This question is broken as originally described. Please ignore it. Everyone will receive 10 free points.

    Note to future James: a better version of this question would have been: Suppose the leader did not propose no-ops for empty slots when it got elected. Describe a sequence of events (possibly including failures) that leads to a state from which a client retransmits a request forever and no further failures occur, but the system never executes the client's request

  3. Consider the following "optimization" to MultiPaxos. If the leader receives a client request that is read-only (e.g. Get in a key-value store), it immediately executes the request on its current copy of the state machine and sends the response to the client. Describe an execution of this "optimized" system that violates linearizability.

    To show a linearizability violation, describe an execution where clients submit requests, MultiPaxos executes those requests (you should describe the events required for MultiPaxos to do this as well), and clients get responses, but those responses are not linearizabile. To show that a set of requests/responses is not linearizable, you must explain why there is no possible global order for the operations, as in problem set 3.

    Hint: There might be multiple nodes that think they are the leader.

  4. Suppose we try to "optimize" the protocol by eliminating phase 1. Any node can declare itself the leader of any ballot consisting of a sequence number and its own node name that is higher than any ballot that node has ever participated in. Describe an execution of this "optimized" system that violates linearizability.

  5. For this problem, consider the protocol including garbage collection and heartbeats. Suppose we "optimize" garbage collection so that the leader declares a slot and value to be garbage as soon as it executes that value on its copy of the state machine, and then the leader then informs all nodes via a new "hey this is garbage" message that the nodes should delete the data in the slot and never consider that slot again. Describe an execution where one node crashes and the system reaches a state where the only remaining two nodes are missing slot data that they need to make further progress.