Due: Friday, January 27, 11:59pm via Gradescope
Each problem is worth 5 points.
The first two problems are about just the view server and the ping messages sent to the view server by all other servers. We call this the View Server Ping protocol:
(Note that while this is similar to part of what you will implement in lab 2, you may have to extend it in some ways. Don't necessarily take anything above as instructions for "you should do it this way in lab 2".)
If a problem says to "describe an infinite execution", you should describe the infinite sequence of events/transitions that occur. Since it is infinite, you cannot just list them, so you have to describe them more generally than that. An event in an infinite execution can be a message delivery, a timer firing, a network failure (drop, duplicate), or a node crashing. Your infinite executions should satisfy "timer fairness", which means that every timer that gets set by a node that doesn't crash eventually gets fired. You do not need to describe the states of your execution, just the events.
If a problem says to "describe a finite execution at a high level", you should describe a finite sequence of events/transitions. You do not necessarily need to list out each event explicitly: instead, you can just summarize several events that lead to a certain intermediate state. Use your judgement and try to focus on the most relevant parts of the execution to the problem. Feel free to start your execution in a "fully initialized view" with a primary and a backup, instead of the initial state. You do not need to worry about timer fairness in finite executions. Also, you do not need to describe the states of your execution, just the events.
Describe an infinite execution of the View Server Ping protocol where a node crashes but the view server detects it as up forever.
Describe an infinite execution of the View Server Ping protocol where a node does not crash, but the view server detects it as down forever.
Consider a version of the full primary-backup protocol but without state
transfer. Instead, as soon as the primary and backup hear from the view
server about the new view, they just start accepting requests.
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 only one
outstanding request at a time), where a later append request returns a result
that contradicts an earlier append request to the same key.
In the full primary-backup protocol (including state transfer), suppose we are in view 3 with a primary \(S_1\) and backup \(S_2\), and state transfer is complete. Client \(C_1\) submits a request \(r\) to \(S_1\) who forwards it to \(S_2\). Now consider two different continuations of this execution.
Suppose \(S_2\) executes the request and sends an acknowledgement to \(S_1\), but before the acknowledgement arrives, \(S_1\) crashes. The view server detects this and wants to move to the next view. Suppose that \(S_3\) is the only idle server available. Answer the following questions about the new view:
Who will be selected as primary in the next view? Who will be selected as backup?
After state transfer completes in the new view, has request \(r\) been executed or not?
Depending on your answer to the previous question, answer the corresponding question below:
If you said that \(r\) has been executed, has \(C_1\) received a response yet? If yes, describe when this response was sent. If no, describe what actions \(C_1\) could take to ensure it gets a response in the future.
On the other hand, if you said \(r\) has not been executed, how would \(C_1\) proceed to get it executed?
Using the same setup as the previous problem, now suppose \(S_2\) crashes before executing \(r\). The view server detects this and wants to move to the next view. Suppose that \(S_3\) is the only idle server available. Answer the following questions about the new view:
Who will be selected as primary in the next view? Who will be selected as backup?
After state transfer completes in the new view, has request \(r\) been executed or not?
Depending on your answer to the previous question, answer the corresponding question below:
If you said \(r\) has been executed, has \(C_1\) received a response yet? If yes, describe when this response was sent. If no, describe what actions \(C_1\) could take to ensure it gets a response in the future.
On the other hand, if you said \(r\) has not been executed, how would \(C_1\) proceed to get it executed?
Based on the previous two scenarios, can \(C_1\) tell 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.
For the rest of the problems, return to the original primary-backup protocol.
Suppose we "optimize" the full primary-backup protocol by allowing the view
server to pick any idle server as the primary for view \(i + 1\) (even a
server that was not the primary or backup of view \(i\)). The rest of the
protocol remains unchanged.
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 only one
outstanding request at a time), where a later append request returns a result
that contradicts an earlier append request to the same key.
Return to the original full protocol, but now suppose we "optimize" it by
allowing the view server to change the view even if the previous view has not
been acknowledged by the primary.
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 only one
outstanding request at a time), where a later append request returns a result
that contradicts an earlier append request to the same key.
In the original protocol, for each of the following properties, categorize it as "unstable", "stable
but not an invariant", or "invariant." Unlike last week, you do not need to
justify your answers in any way.
We use the phrase "current view" to mean "the view that the view server is
currently advertising". Notice that the "current view" changes when the view
server decides to do a view change.
In the original protocol, for each of the following properties, categorize it as "unstable", "stable
but not an invariant", or "invariant." Unlike last week, you do not need to
justify your answers in any way.
We use the phrase "current view" to mean "the view that the view server is
currently advertising". Notice that the "current view" changes when the view
server decides to do a view change.
The following two bonus questions were added after lecture on Friday 1/21/23. They are also worth 5 points, which means this problem set totals 60 points, more than the 50 promised on the syllabus. This only helps you, since the final grade cutoffs on the syllabus remain the same. As with anything in this class, feel free not to do these problems.
Suppose we are in a view with primary \(S_1\) and backup \(S_2\) and that
state transfer has completed. Then the view server thinks that \(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 containing information
about the new view takes a long time to arrive at \(S_2\). Since \(S_1\) is
not actually crashed, clients can continue to execute requests by sending
them to \(S_1\), who forwards to \(S_2\), who acknowledges, and so on, as
normal.
Explain briefly why is it not a bug that the old view can keep executing
even after the view server has moved to a new view. In particular,
explain why the new view and the old view cannot operate independently
and diverge from each other.
Suppose we "optimize" the protocol so that when the primary receives a client
request it first executes that request locally, immediately replies to the
client, and then forwards it to the backup and waits for the backup's
acknowledgement before executing any further requests.
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 only one
outstanding request at a time), where a later append request returns a result
that contradicts an earlier append request to the same key.