Due: Friday, October 13, 11:59pm via Gradescope
In Lecture, we considered several variants of RPC:
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.
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.
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.
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.
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.
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.
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.
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.
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
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: