Problem Set 2: Primary-backup and linearizability

Due: Tuesday, October 20, 6:30pm. Individual work. Submit a PDF of your answers on Gradescope.

Background

Throughout this problem set, you should assume the "standard 552 fault model": asynchronous unreliable message delivery (messages can be delayed, dropped, reordered, or duplicated, but not corrupted) with fail-stop node crashes.

An event is a message delivery, a timer firing, a message failure (a drop or a duplicate), or a node crash. Nodes that crash can never participate in future events.

An execution is a sequence of events. When a problem asks you to "describe an execution", it means to list the events. You do not need to describe the states along the way, just the events.

Some problems ask you "describe an infinite execution". Since it is infinite, you cannot actually list the events. Instead, you should describe them more generally, for example as a pattern that repeats forever. All infinite executions in this problem set must satisfy timer fairness: every timer set by a node that does not crash eventually fires.

Some problems ask you to "describe a finite execution at a high level". In this case, you do not need to explicitly list every event. Instead, you may summarize several events that lead to an intermediate state. Focus on the parts of the execution that are relevant to the problem. When describing at a high level, you may start your description in a "fully initialized view" with a non-null primary and a non-null backup instead of the initial state. Timer fairness does not apply to finite executions.

Definition

A request has been executed on a node's application if it contributed to the history of commands that produced that application's state.

This is a somewhat subtle definition! If a request's effects later get overwritten by a subsequent request (for example, a put to a key gets overwritten by a later put to the same key), then the first request is still "executed" because it contributed to the history that led to this state. On the other hand, if the primary-backup state transfer mechanism overwrites the entire application in such a way that the request was "never there", then that request is no longer executed.

The View Server Ping protocol

The first problem is about just the view server and the ping messages sent to it by all other servers. We call this the View Server Ping protocol:
- There are two kinds of nodes: one view server and any number of other servers.
- State:
  - View server: pingSet, the set of servers that have pinged since the last PingCheckTimer; and aliveSet, the set of servers considered alive.
  - Other servers: no relevant state.
- Messages:
  - Ping, from a server to the view server. The message has no data. When the view server receives it, it adds the sender to pingSet.
- Timers:
  - SendPingTimer, set by each non-view server. When it fires, the server sends a Ping to the view server and resets the timer.
  - PingCheckTimer, set by the view server. When it fires, the view server overwrites aliveSet with pingSet, empties pingSet, and resets the timer.
This is similar to part of what you will implement in Lab 2, but not identical: for example, Lab 2's pings have view numbers but the protocol in this problem does not. Do not interpret this problem as giving you instructions about how to do the lab.
1. Describe an infinite execution of the View Server Ping protocol where a server crashes but the view server considers it alive forever. Be sure your execution satisfies timer fairness.
2. Describe an infinite execution of the View Server Ping protocol where a server does not crash, but the view server considers it down forever. Be sure your execution satisfies timer fairness.

Primary-backup

For this problem only, consider a modified version of the "full" primary-backup protocol where we remove the state transfer part of the protocol. Instead, as soon as the primary and backup hear about a new view from the view server, they simply start accepting requests. Call this protocol "primary-backup without state transfer".

Describe at a high level a finite execution of this system with only one client that submits only Append operations on the key foo, and only submits one request at a time, where a later append returns a result that contradicts an earlier append to the same key. (Hint: Use a view change.)
This problem is about the (unmodified) full primary-backup protocol. Suppose we are in view 3 with primary \(S_1\) and backup \(S_2\), and state transfer is complete. Client \(C_1\) submits a request \(r\) to \(S_1\), which forwards it to \(S_2\). Call this point in the execution the pre-continuation point. Now consider two different continuations:
1. Starting from the pre-continuation point, suppose \(S_2\) executes \(r\) and sends an acknowledgment to \(S_1\), but before the acknowledgment arrives, \(S_1\) crashes. The view server detects this and moves to the next view. \(S_3\) is the only idle server available.
  - Who is the primary of the next view? Who is the backup?
  - After state transfer completes in the new view, has \(r\) been executed on the new primary's application or not?
  - If you said \(r\) has been executed: has \(C_1\) received a response yet? If yes, say when it was sent. If no, say what \(C_1\) can do to get one. If you said \(r\) has not been executed: how can \(C_1\) get it executed?
2. Starting from the pre-continuation point, now suppose \(S_2\) crashes before executing \(r\). The view server detects this and moves to the next view. \(S_3\) is the only idle server available.
  - Who is the primary of the next view? Who is the backup?
  - After state transfer completes in the new view, has \(r\) been executed on the new primary's application or not?
  - If you said \(r\) has been executed: has \(C_1\) received a response yet? If yes, say when it was sent. If no, say what \(C_1\) can do to get one. If you said \(r\) has not been executed: how can \(C_1\) get it executed?
3. Using the two previous parts, can \(C_1\) tell immediately whether or not its request has been executed? If yes, describe how. If not, explain why not, and how \(C_1\) can still make progress without knowing which scenario occurred.
Each part of this problem proposes an "optimization" to the full primary-backup protocol; the rest of the protocol is unchanged. For each one, describe at a high level a finite execution of the system with only one client that submits only Append operations on the key foo, and submits only one outstanding request at a time, where a later append returns a result that contradicts an earlier append to the same key.
1. The view server may pick any idle server as the primary of view \(i+1\), even one that was neither the primary nor the backup of view \(i\). The new primary still does state transfer to the new backup.
2. The view server may change the view even if the previous view has not been acknowledged by its primary.
3. When the primary receives a client request, it first executes the request locally and immediately replies to the client, and only then forwards the request to the backup and waits for the backup's acknowledgment before executing any further requests.
Suppose we are in a view with primary \(S_1\) and backup \(S_2\), and state transfer has completed. The view server thinks \(S_1\) is down, so it moves to the next view, promotes \(S_2\) to primary, and selects idle server \(S_3\) as the new backup. But the message announcing the new view takes a long time to reach \(S_2\). Since \(S_1\) has not actually crashed, clients keep executing requests through \(S_1\), which forwards to \(S_2\), which acknowledges, and so on, as normal.

Explain briefly (a few sentences) why it is not a bug that the old view can keep executing requests after the view server has moved on to the new view. In particular, explain why the new view and the old view cannot operate independently and diverge from each other.

Invariant, stable, or unstable

The next two problems ask whether certain properties can be violated in the full primary-backup protocol. Given a property \(P\), categorize it as one of:
- invariant, "always true": in every execution, \(P\) holds in every state.
- stable, "sometimes false, but once true it stays true": in every execution, once \(P\) becomes true it remains true for the rest of the execution; and \(P\) is false at the start of some execution (otherwise it would be an invariant).
- unstable, "it can go from true to false": in some execution, \(P\) is true at some point and false later.
If you answer "unstable", justify it by describing at a high level a finite execution where the property is true at one point and false later. If you answer "invariant" or "stable", briefly justify why the property cannot become false after being true; then, if you say "invariant", say why it is true in the initial state, or, if you say "stable", why it is false in the initial state.

The current view is the view the view server is currently advertising. (So, when the view server changes to a new view, the new view becomes "current".)
1. "Server \(S_1\) is the primary in view 3."
2. "Server \(S_1\) is the primary of the current view."
3. "If the current view number is greater than 0, then the current view has a primary."
4. "If the current view number is greater than 0, then the current view has a backup."
5. "If the current view number is greater than 0, then the primary of the current view has not crashed."
Same instructions as the previous problem.
1. "If a response message with sequence number \(n\) has been sent to client \(c\), then the corresponding request has been executed on the current view's primary's application."
2. "If \(S_1\) is the primary of view \(i\) and \(S_2\) is the backup of view \(i\), and \(S_2\) has sent \(S_1\) a forwarded-request acknowledgment with view number \(i\) for request \(r\), then \(r\) has been executed on \(S_2\)'s application."
3. "If \(S_1\) is the primary of view \(i\) and \(S_2\) is the backup of view \(i\), and \(S_2\) has sent \(S_1\) a forwarded-request acknowledgment with view number \(i\) for request \(r\), then \(r\) has been executed on the current view's backup's application."
4. (Recall that the primary-backup protocol replicates the entire AMOApplication, not just the key-value store.) "If \(S_1\) is the primary of view \(i\) and \(S_2\) is the backup of view \(i\), and \(S_2\) has sent \(S_1\) a forwarded-request acknowledgment with view number \(i\) for request \(r\), then \(S_2\)'s AMOApplication has an entry for \(r\)'s client with a sequence number at least as large as \(r\)'s."

Linearizability

Recall the definition: an execution is linearizable if there is a global order on client operations such that (1) the responses sent to clients are the same as if the operations were executed one at a time in that order, (2) the order agrees with the order in which each client issued its own requests, and (3) if a client receives a response and later some client starts a new request, the new request comes after the completed one in the global order.

To show that an execution is linearizable, describe the global order on operations (an operation is a request paired with its response) and briefly say why it satisfies (1), (2), and (3).

To show that an execution is not linearizable, explain why no order satisfying (1), (2), and (3) exists. The easiest way is to exhibit a cycle: for example, "by (1), operation A must come before B, but by (3), B must come before A."

For each of the executions below, determine whether the execution is linearizable. Justify your answer either way as described above. You should assume that each execution starts from an initially empty key-value store, and that the operations shown in the execution are the only operations executed on the system.
1. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_1\) sends Append(k, x)
  - \(C_2\) sends Get(k)
  - \(C_2\) receives GetResult(x)
  - \(C_1\) receives AppendResult(x)
2. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_1\) sends Append(k, x)
  - \(C_2\) sends Get(k)
  - \(C_1\) receives AppendResult(x)
  - \(C_2\) receives KeyNotFound()
3. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_1\) sends Append(k, x)
  - \(C_1\) receives AppendResult(x)
  - \(C_2\) sends Get(k)
  - \(C_2\) receives KeyNotFound()
4. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_2\) sends Get(k)
  - \(C_2\) receives GetResult(x)
  - \(C_1\) sends Append(k, x)
  - \(C_1\) receives AppendResult(x)
5. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_1\) sends Append(k, x)
  - \(C_2\) sends Append(k, y)
  - \(C_2\) receives AppendResult(y)
  - \(C_1\) receives AppendResult(yx)
6. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_1\) sends Append(k, x)
  - \(C_2\) sends Append(k, y)
  - \(C_2\) receives AppendResult(y)
  - \(C_1\) receives AppendResult(xy)
7. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_1\) sends Append(k, x)
  - \(C_1\) receives AppendResult(yx)
  - \(C_2\) sends Append(k, y)
  - \(C_2\) receives AppendResult(xy)
8. Determine whether the following execution is linearizable. Justify your answer.
  - \(C_1\) sends Append(k, x)
  - \(C_2\) sends Get(k)
  - \(C_2\) receives GetResult(x)
  - \(C_3\) sends Get(k)
  - \(C_3\) receives KeyNotFound()
  - \(C_1\) receives AppendResult(x)