CSE 452: Distributed Systems

Problem Set 1: RPC and network thinking

Due: Friday, October 13, 11:59pm via Gradescope

In Lecture, we considered several variants of RPC:

  • Naive RPC
  • Naive RPC modified to use per-client sequence numbers on requests and responses so that different requests and responses can be distinguished.
    • Call this one "Naive RPC with request identifiers"
  • At least once RPC
    • Naive RPC with request identifiers PLUS the client retransmits its requests until it gets a response (or gives up).
  • At most once RPC
    • The server tracks which requests it has already executed and retransmits the responses if it receives the same request again.
  • Exactly once RPC
    • At most once RPC PLUS the client retransmits its requests until it gets a response (or gives up).

Unless stated otherwise, assume our default fault model for this course: asynchronous unreliable message delivery with fail-stop node crashes.

Each problem is worth 7 points.

  1. In the "Naive RPC with request identifiers" protocol, is it possible for a client to send a request and get a response to that request from the server, but that request wasn't actually executed on the server? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

  2. In the "Naive RPC with request identifiers" protocol, is it possible for a client to send a request and get a response to that request from the server, but that request was executed on the server more than once? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

  3. In the "Naive RPC with request identifiers" protocol, suppose a client sends a request and doesn't get a response. Is it possible that the request wasn't executed by the server? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

  4. In the "Naive RPC with request identifiers" protocol, suppose a client sends a request and doesn't get a response. Is it possible that the request was executed by the server? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

  5. In the "Naive RPC with request identifiers" protocol, suppose a client sends a request and doesn't get a response. Is it possible that the request was executed more than once by the server? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

  6. In the "At least once RPC" protocol, is it possible for a client to send a request and get a response to that request from the server, but that request was executed on the server more than once? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

  7. In the unoptimized "At most once RPC" protocol, is it possible for a client to send a request and get a response to that request from the server, but that request was executed on the server more than once? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

  8. In the unoptimized "At most once RPC" protocol, suppose a client sends a request and doesn't get a response. Is it possible that the request wasn't executed by the server? If yes, briefly describe an execution where that occurs. If not, explain why not in one sentence.

The next problems are about an optimization to the "At most once RPC" protocol from lecture. To recap the unoptimized protocol: the server stores a map

\[ (\mathrm{client\_id}, \mathrm{seqnum}) \mapsto \mathrm{response} \]

Then, 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.

Unlike the labs, this protocol does not assume that there is only one outstanding request per client. The server's map data structure has enough information in it to handle multiple simultaneous requests from a single client.

In lab 1, you will optimize this protocol by taking advantage of the assumption that there is only one outstanding request per client. Here, we consider an alternative optimization that does not make that assumption:

  • When a client receives a response to some sequence number \(s\), it sends a "response acknowledgement" message for \(s\) to the server.
  • When the server receives a response acknowledgement from a client \(c\) for some sequence number \(s\), it deletes the map entry for \((c, s)\) (if any).

  1. Describe briefly (at most a few sentences) how much space this optimization saves on the server compared to the unoptimized protocol.
  2. Does the above optimization correctly implement at most once semantics? If yes, explain in a few sentences how it guarantees that a request is never re-executed. If not, briefly describe an execution where a request from the same client and with the same sequence number can be executed twice by the server.