Problem Set 4: Linearizability and SingleDecree 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.
 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()}\)
 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()}\)
 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)}\)
 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)}\)
SingleDecree Paxos
Here is a description of singledecree 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 singledecree 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 highestballoted 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
nonNone 2b message, then let \(v\) be the value of the
highestballoted 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:
 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:
 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 highlevel 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.
 Suppose \(k=1\), \(n=3\), and \(l=1\). Describe an execution of singledecree 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})\)