# Problem Set 1: Intro; RPC Due: Friday, January 7, 11:59pm via Gradescope A challenge for distributed systems is that neither computers nor networks are perfect. Computers can crash or be slow, and networks can drop packets, reorder packets, or be slow. While it might seem like we could use TCP to address many of these issues, since it is designed to retransmit missing packets, TCP itself can fail – for example, if a client is in the middle of sending some operation to a server, and the WiFi router crashes, the TCP connection might reset. When the WiFi reconnects, should the client resend any operation that might have been in progress? If it doesn’t, maybe those operations never reached the server. If it does, what if those operations previously got through and were completed? Doesn’t that risk doing some operations twice? In this exercise, we will consider how to coordinate the client and server such that the intended behavior occurs. Suppose a client sends a sequence of requests to the server: a, b, c, d, e (without waiting for anything from the server between requests). Assume the server immediately acknowledges each successfully received message (before it executes the request), and the client resends any request that is not acknowledged within some timeout (and if the resent request is not acknowledged after the timeout expires again, the client will resend the request a third time, and so on, indefinitely, until it gets an acknowledgement). (Note in the labs each client waits for the response to its request before sending the next message—here the client does not wait.) Later, when the server has executed the request it will send a *response*. To emphasize: We are using the words "response" and "acknowledgements" to mean different things in this problem set. An acknowledgment is something the server sends immediately when receiving a request. A response is what the server sends when it is done *executing* the request. What can go wrong? This problem considers several different network fault models. Unless otherwise noted, assume (unrealistically!) the network reliably delivers messages in order and with a round-trip time of less than the client's retransmission timeout. Also assume (unrealistically!) that no nodes crash. Read each subproblem carefully to note how it changes this default fault model. Each problem is worth 5 points. 1. In the default fault model above (in order, reliable delivery, no node crashes), can the server receive any sequence of requests *besides* a, b, c, d, e? 1. Suppose the network can drop messages, but the messages that don't get dropped are still delievered in order. Is it possible for the server to see the messages in this order: a, b, d, e, c? If yes, describe in one sentence a sequence of events that leads to this outcome. If no, explain in one sentence why not. 1. Same fault model as the previous question. Is it possible for the server to see the messages in this order: e, d, c, b, a? If yes, describe in one sentence a sequence of events that leads to this outcome. If no, explain in one sentence why not. 1. Now starting from the default fault model again, this time assume messages can be delayed arbitrarily (but not dropped, duplicated, or reordered) by the network. Is it possible for the server to see the messages in this order: a, b, c, d, e, c, d, e? If yes, describe in one sentence a sequence of events that leads to this outcome. If no, explain in one sentence why not. (Clarification: this is a bit of a strange fault model, because if we *knew* this was how the network behaved, there would be no use for retransmission. Nevertheless, please answer the question about a client who retransmits under this fault model.) 1.

Now starting from the default fault model again, this time suppose packets can be reordered by the network. Is there any sequence of messages that is impossible in this fault model? For the rest of the questions, assume the network can drop, delay, and reorder messages. 1.

Suppose a client receives an acknowledgment to a request message. Does the client know that the request was received? Why or why not in one sentence? 1. Suppose a client receives a *response* to a request. Does the client know that the request was received? Why or why not in one sentence? 1. Suppose a client receives an *acknowledgment* to a request message. Does the client know that the request was executed? Why or why not in one sentence? 1. Suppose a client receives a *response* to a request. Does the client know that the request was executed? Why or why not in one sentence? 1. Suppose a client does *not* receive an acknowledgement to a request message. Does the client know that the request message was *not* received? Why or why not in one sentence? 1. (This feedback question is worth 5 additional points, so there are more points available than originally announced. It's optional, just like everything else.) How much time did you spend on this problem set? Feel free to include other feedback here.