# Problem Set 2: RPC and Primary-Backup Due: Friday, January 21, 11:59pm via Gradescope Each question is worth 5 points unless otherwise noted. There are slightly more points available (65) than originally advertised (50), so feel extra free to skip a few problems if you want. Remember, your grade is determined by points earned, not points missed. ## RPC In Lectures 3 and 4, we proposed a basic implementation strategy for at most once RPC semantics where the server keeps track of a map \[ (\mathrm{client\_id}, \mathrm{seqnum}) \to \mathrm{response} \] When the server receives a request from client \(c\) with sequence number \(s\), it first checks if \((c, s)\) is in its map. If so, it returns the cached response. Otherwise, it executes the request to compute a response \(r\) and inserts \((c, s)\mapsto r\) into its map. Note that this is different than the strategy used in lab 1, where the server stores at most one request per client. 1. Roughly how much space does the server need to store the map above? (Your answer might be phrased as something like "The server needs space proportional to the size of the largest request it has received." (but that is not the right answer). Roughly one sentence.) 1. Now consider the following proposed optimization to the protocol. * When a client receives a response to some sequence number \(s\), it sends a "response acknowledgment" message for \(s\) to the server. * When the server receives a response acknowledgment from a client \(c\) for some sequence number \(s\), it deletes the map entry for \((c, s)\) (if any). How much space does the server need now? (Roughly one sentence.) 1. Does the above optimization correctly implement at most once semantics? If so, explain in a few sentences how it guarantees that a request is never re-executed. If not, describe a scenario where a request from the same client and with the same sequence number can be executed twice by the server. ## Primary-Backup The next several questions are about the primary-backup protocol described in lectures 5 and 6, in section from week 2, and in lab 2. Lecture 6 in particular emphasized the following important correctness constraint the protocol:

When a view change occurs, the new primary's state must reflect the effects of all client requests that were responded to by primary of the old view.

The protocol design described in lecture/section/lab follows the rule "the primary of view \(i+1\) must be either the primary or backup of view \(i\)". Consider the following scenarios: 1. Suppose the system is fully initialized in a view with both a primary and a backup. (State transfer has finished and the primary has acknowledged the new view to the server.) Then the primary fails and the backup is promoted by the view server to primary in the next view. Explain in a few sentences why the protocol guarantees the new primary's state reflects all requests responded to by the old primary. 1. Same failure scenario as previous problem. Is it possible that the old primary *received* a request from a client that is not reflected in the new primary's state? If yes, explain in a few sentences how such a scenario could arise. If not, explain in a few sentences why it is impossible. 1. Same failure scenario as previous problem. Suppose a client is using the system while the failure scenario occurs. It had submitted a request to the primary in the old view, but never heard back despite retransmitting several times. Later, the client learns from the view server about the new view. * Explain why it is possible for the client's request to be reflected in the new primary's state. (A sentence or two.) * Also explain why it is possible for the client's request to *not* be reflected in the new primary's state. (A sentence or two.) 1. (10 points) Suppose we "optimize" the protocol by allowing the view server to pick any node as the primary for view \(i+1\) (even a node that was not the primary or backup of view \(i\).) Describe a scenario that violates the correctness constraint above *in a client-observable way*. In other words, describe a sequence of events that leads to a client request being responded to in view \(i\), but not reflected in the state of the primary of view \(i + 1\) that is used to respond to a client request in view \(i+1\). You can assume view \(i\) is fully initialized with a primary and a backup. Be sure your sequence of events involves two client requests, both of which are responded to. The first one's effect should be incorrectly missing from the second one. (Hint: It may be simplest to describe a scenario where the application being replicated is a key-value store. Show that some later `get` operation does not reflect the effects of previous `put`s. Be sure to follow the protocol closely except for the broken "optimization" proposed in this problem.) 1. (10 points) Return to the original 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 a sequence of events that violates the correctness constraint above in a client observable way. 1. (You may collaborate with your lab 2 partner on this question. Both of you can submit identical answers to this question (but not other questions) if you want.) (10 points) In the failure scenario from Problem 6, the client is not sure if their request was executed or not. In the RPC protocol from lab 1, clients could always ensure the command was executed by retransmitting the request that they had not heard a response to yet. Explain how you plan to support this scenario in your solution to lab 2. Be sure to explain how the new primary will have enough information to correctly retransmit the response computed by the old primary. ## Feedback 1. (This feedback question is also worth 5 points. It's optional, just like everything else.) How much time did you spend on this problem set? Feel free to include other feedback here.