CSE 452: Distributed Systems

Problem Set 4: Linearizability and Single-Decree Paxos

Due: Friday, February 17, 11:59pm via Gradescope

Each problem is worth 10 points to make up for the fact that James deleted a problem set.

Linearizability

Recall the definition of linearizability: an execution is linearizable if their exists a global order on client operations such that: (1) the responses sent to clients return the same answers as if the operations were executed in the global order (2) the ordering agrees with the order each client sent their own requests in and (3) if a client receives a response and then later another client starts a new request, then the new request comes after the first request in the global order.

To show that an execution is linearizable, you must describe the global order on operations. (An operation is a pair of a request and its response.) Then explain (briefly) why the global order satisfies requirements (1), (2), and (3) above.

To show that an execution is not linearizable, you must explain why there is no possible global order satisfying (1), (2), and (3) above. The easiest way to do this is to describe a cycle in the "dependency graph" of the execution. For example, you might say something like "because of requirement (1), operation A has to come before operation B in the global order, but because of requirement (2), operation B has to come before operation A." These contradicting requirements show that no such global order exists.

  1. Show that the following execution is linearizable.
    • Client \(C_1\) sends request \(\mathtt{Append(k, x)}\)
    • Client \(C_2\) sends request \(\mathtt{Get(k)}\)
    • Client \(C_1\) receives response \(\mathtt{AppendResult(x)}\)
    • Client \(C_2\) receives response \(\mathtt{KeyNotFound()}\)
  2. Show that the following execution is not linearizable
    • Client \(C_1\) sends request \(\mathtt{Append(k, x)}\)
    • Client \(C_1\) receives response \(\mathtt{AppendResult(x)}\)
    • Client \(C_2\) sends request \(\mathtt{Get(k)}\)
    • Client \(C_2\) receives response \(\mathtt{KeyNotFound()}\)
  3. Show that the following execution is linearizable
    • Client \(C_1\) sends request \(\mathtt{Append(k, x)}\)
    • Client \(C_2\) sends request \(\mathtt{Append(k, y)}\)
    • Client \(C_2\) receives response \(\mathtt{AppendResult(y)}\)
    • Client \(C_1\) receives response \(\mathtt{AppendResult(yx)}\)
  4. Show that the following execution is not linearizable
    • Client \(C_1\) sends request \(\mathtt{Append(k, x)}\)
    • Client \(C_2\) sends request \(\mathtt{Append(k, y)}\)
    • Client \(C_2\) receives response \(\mathtt{AppendResult(y)}\)
    • Client \(C_1\) receives response \(\mathtt{AppendResult(xy)}\)

Single-Decree Paxos

Here is a description of single-decree Paxos. (We describe each role as a separate node. In lab 3, you will combine all three roles on each node.)

A ballot is a pair of a ballot number and a proposer id. Ballots are ordered by first comparing ballot numbers and if those are equal, then comparing proposer ids.

  • Nodes: there are \(k\) proposers, \(n\) acceptors, and \(l\) learners
    • Proposer: will refer to the current proposer's id as \(i\) (which will satisfy \(0 \le i < k\)).
      • state:
        • \(\mathtt{current\_ballot\_num}\): current ballot number, an integer, initially 0
        • \(\mathtt{votes}\): set of (sender, PrepareResponse (1b) message) pairs received for current ballot number, initially empty
          • in this description of single-decree Paxos, the proposer uses the size of the \(\mathtt{votes}\) set to remember whether or not is has already proposed a value in this ballot number yet or not. if the size of \(\mathtt{votes}\) is greater than \(\lfloor n/2 \rfloor\), then the proposer has already proposed. if it is less than or equal to \(\lfloor n/2 \rfloor\), then the proposer has not proposed in this ballot number yet.
    • Acceptor:
      • state:
        • \(\mathtt{promised\_ballot}\): the highest ballot this acceptor has ever sent a 1b message for, optional, initially None
        • \(\mathtt{last\_accepted}\): the highest-balloted AcceptResponse (2b) message ever sent by this acceptor, optional, initially None
    • Learner:
      • state:
        • \(\mathtt{accepts}\): set of all (sender, AcceptRessponse (2b) message) pairs ever received, initially empty
  • Messages
    • Prepare (also known as "1a")
      • contents:
        • a ballot (i.e., a pair of a ballot number and a proposer id)
      • sent from a proposer to an acceptor
      • when received:
        • let \(b\) be the ballot on the incoming Prepare message
        • the acceptor ignores the message if \(\mathtt{promised\_ballot}\) is not None and \(b\) is less than or equal to \(\mathtt{promised\_ballot}\)
        • otherwise, the acceptor sets \(\mathtt{promised\_ballot}\) to \(b\), and sends a PrepareResponse message back to the proposer containing the incoming Prepare message's ballot and \(\mathtt{last\_accepted}\).
    • PrepareResponse (also known as "1b")
      • contents:
        • a ballot
        • an optional AcceptResponse (2b) message
      • sent from acceptor to proposer
      • when received:
        • let \(b\) be the ballot on the incoming PrepareResponse message
        • the proposer ignores the message if \(b\) is not equal to \((\mathtt{current\_ballot\_num}, i)\) where \(i\) is the proposer's id
        • let \(m\) be the old size of the proposer's \(\mathtt{votes}\) set
        • the proposer adds the pair (sender, incoming PrepareResponse message) to the \(\mathtt{votes}\) set
        • let \(m^\prime\) be the new size of the proposer's \(\mathtt{votes}\) set
        • if \(m \le \lfloor n/2 \rfloor\) and \(m^\prime > \lfloor n/2 \rfloor\), then:
          • if every element of \(\mathtt{votes}\) contains None as its 2b message, then let \(v\) be any value the proposer wants.
          • otherwise, if there is some element of \(\mathtt{votes}\) with a non-None 2b message, then let \(v\) be the value of the highest-balloted 2b message from any 1b message in \(\mathtt{votes}\).
          • send an Accept message containing \(((\mathtt{current\_ballot\_num}, i), v)\) to all acceptors, where \(i\) is the proposer's id.
    • Accept (also known as "2a")
      • contents:
        • a ballot
        • a value
      • sent from proposer to acceptor
      • when received:
        • let \(b\) and \(v\) be the ballot and value on the incoming Accept message
        • the acceptor ignores the message if \(\mathtt{promised\_ballot}\) is not None and \(b\) is strictly less than to \(\mathtt{promised\_ballot}\)
        • the acceptor sends an AcceptResponse message containing \((b, v)\) to all learners
        • if \(\mathtt{last\_accepted}\) is None or if the ballot of \(\mathtt{last\_accepted}\) is less than \(b\), then the acceptor sets \(\mathtt{last\_accepted}\) to \((b, v)\).
    • AcceptResponse (also known as "2b")
      • contents:
        • a ballot
        • a value
      • sent from acceptor to learner
      • when received
        • the learner adds the pair (sender, incoming AcceptResponse) message to \(\mathtt{accepts}\)
  • Spontaneous actions
    • start new proposal
      • at any time, a proposer can decide to start a new proposal by incrementing its \(\mathtt{current\_ballot\_num}\), clearing its \(\mathtt{votes}\) set, and sending a Prepare (1a) message with ballot \((\mathtt{current\_ballot\_num}, i)\) (where \(i\) is the proposer's id) to all acceptors.

(A "spontaneous action" is just a high-level way of describing something that you would do with a timer in practice. It means the proposer can do it whenever it wants to.)

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}(v)\) to mean that there exists a ballot \(b\) and a set of acceptors \(A\) such that the size of \(A\) is greater than \(\lfloor n/2\rfloor\) and every acceptor in \(A\) has sent an AcceptResponse (2b) message with contents \((b, v)\).

To "describe an execution", list the events that happen. An event can be a "spontaneous action" or a message delivery. No need to explain the events, just list them.

  1. Suppose \(k=1\), \(n=3\), and \(l=1\). Describe an execution of single-decree Paxos that reaches a state where \(D(Chosen(v))\) but not \(K_L(Chosen(v))\), where \(L\) is the one learner.
    • Recall from the distributed knowledge paper that \(D(x)\) means "looking down from a bird's eye view of the system, one can see that \(x\) holds".
    • \(K_N(x)\) means "node \(N\) knows that \(x\) holds"

For each state below, say whether the state is reachable or not. If yes, describe an execution that reaches it. On the other hand, if the state is not reachable, describe an invariant that is false in this state, and explain why your invariant is an invariant in one sentence.

We omit some pieces of the state (often the proposer and learner). In that case, you should say whether there is any state matching the parts we did not omit that is reachable, or whether all such states are unreachable. (Still describing an execution or an invariant (and its explanation) as above.)

Suppose \(k=2\), \(n=3\), and \(l=2\), and let \(P_1\) and \(P_2\) be the proposers, \(A_1\), \(A_2\), and \(A_3\) be the acceptors, and \(L_1\) and \(L_2\) be the learners. In the ordering of ballots, suppose \(P_1 < P_2\). Let \(v\) and \(w\) be values such that \(v \ne w\).

    • \(A_1: (\mathtt{promised\_ballot} = (1, P_1), \mathtt{last\_accepted} = ((1, P_1), v))\)
    • \(A_2: (\mathtt{promised\_ballot} = (1, P_1), \mathtt{last\_accepted} = ((1, P_1), w))\)
    • \(A_3: (\mathtt{promised\_ballot} = \mathtt{None}, \mathtt{last\_accepted} = \mathtt{None})\)


    • \(A_1: (\mathtt{promised\_ballot} = (1, P_2), \mathtt{last\_accepted} = ((1, P_1), v))\)
    • \(A_2: (\mathtt{promised\_ballot} = (1, P_2), \mathtt{last\_accepted} = ((1, P_2), w))\)
    • \(A_3: (\mathtt{promised\_ballot} = \mathtt{None}, \mathtt{last\_accepted} = \mathtt{None})\)


    • \(A_1: (\mathtt{promised\_ballot} = (1, P_1), \mathtt{last\_accepted} = ((1, P_1), v))\)
    • \(A_2: (\mathtt{promised\_ballot} = \mathtt{None}, \mathtt{last\_accepted} = ((1, P_1), v))\)
    • \(A_3: (\mathtt{promised\_ballot} = (1, P_1), \mathtt{last\_accepted} = \mathtt{None})\)


    • \(A_1: (\mathtt{promised\_ballot} = (1, P_1), \mathtt{last\_accepted} = ((1, P_1), v))\)
    • \(A_2: (\mathtt{promised\_ballot} = \mathtt{None}, \mathtt{last\_accepted} = ((1, P_1), v))\)
    • \(A_3: (\mathtt{promised\_ballot} = \mathtt{None}, \mathtt{last\_accepted} = \mathtt{None})\)


    • \(A_1: (\mathtt{promised\_ballot} = (1, P_1), \mathtt{last\_accepted} = ((1, P_1), v))\)
    • \(A_2: (\mathtt{promised\_ballot} = (1, P_2), \mathtt{last\_accepted} = ((1, P_2), w))\)
    • \(A_3: (\mathtt{promised\_ballot} = \mathtt{None}, \mathtt{last\_accepted} = \mathtt{None})\)