CSE550 Problem Set #2

[ Summary | Paxos | Lock Service | Submission |

Summary

In order to build an highly available service such as Google's MegaStore/Spanner storage systems or Facebook's social networking site, one of the most important building blocks is to provide a way in which the underlying data is replicated and can be accessed even in the presence of failures. To this end, this assignment will require you to build a replicated state machine based on Paxos. The focus of this assignment will be on the backend Paxos algorithms and in designing and building a highly reliable distributed storage system. Beyond the base requirements outlined in this document, this assignment is open-ended and we would like to give you substantial flexibility in design and implementation choices, as well as the ability to explore the features of Paxos-based systems that interest you. Specifically, you can choose your implementation language. Because of the open-ended nature of this assignment, deliverables include (a) a working implementation, (b) documentation of your system and design decisions in a writeup, and (c) a presentation of your system in a live demo to a course TA.

Paxos Implementation

The core of the assignment is to develop a Paxos replicated state machine. The basic idea of the Paxos RSM is described in Section 3 of the "Paxos made simple" paper by Lamport. A quick summary of the implementation strategy is as follows:

• Model the service that you are implementing as a deterministic state machine whose behavior or output is simply a function of its previous state and any inputs received from the user or environment in the current step.
• Implement a multi-instance Paxos algorithm to come to a consensus on the sequence of input values that the service receives in a consistent and reliable way. That is, the i^th instance of Paxos determines the i^th input or command received by the service.
• From a client perspective, it can send the service request to any of the nodes that comprise the Paxos group. The node that receives the request tries to pass a Paxos instance using the received value. If it fails to pass it with the current instance, it tries to pass as the consensus value for a subsequent instance.
• Run a copy of the underlying state machine on each of the nodes that belongs to the Paxos group. Each state machine executes the i^th command once it is stable and after it has executed all previous commands. A command is stable if it is the chosen value for that instance of Paxos. Once the command is stable and the state machine has processed it, a response is sent back to the client.

You can organize your code in whatever mechanism that you think is appropriate. For example, you could have a single entity that serves all three roles of proposer, acceptor, and listener. Include a discussion of design issues that came up in your writeup, as well as a rough overview of what your code does.

The implementation of Paxos should be robust to message loss and node failures and should be able to make progress as long as a majority of nodes are online. However, given the short timeline for this assignment, we don't require the following features in your Paxos implementation:

• Node recovery. Assume that once a node fails then it will never recover. This means that there is no need for a persistent log to disk.
• Resending messages. Although your implementation should still be able to make progress given a reasonable threshold of lost messages, your implementation does not need to resend messages that may have been lost.

Lock Service

Demonstrate the correctness of your Paxos implementation by developing a simple lock server as the replicated state machine. The lock server should have the following functionality:

• It manages the lock status for a number of locks.
• It supports a blocking lock(x) operation that returns when x is assigned to the requesting client. If x is currently assigned to a different client, the request is queued at the state machine. A reply is sent only when the lock becomes available and is assigned to the requesting client.
• It supports a unlock(x) operation that frees up the lock.

• the identity of the Paxos group members can be hardcoded at the client,
• clients will be well-behaved, so that your system does not need to handle deadlock, clients that fail after acquiring a lock, etc.
• the client to server communications are reliable, so you do not have to worry about issues such as atmost-once or atleast-once semantics for the delivery of client requests or responses.

When you're ready to turn in your assignment, do the following:

1. Create a directory called "problemset2". In it, you should have the code for the assignment, a README.txt file, and a writeup.

2. The README.txt file should contain the name, student number, and UW email address for all team members, as well as instructions on how to launch your server.

3. A major component of your grade will be based on a project write-up, in which your group should explain the protocol and any relevant implementation details. You should include, at a minimum, the following:
   • a detailed description of your group's implementation
   • any assumptions you made
   • how to use your implementation
   • any outstanding issues
   • anything else that you feel is important to discuss (e.g. quirks, interesting behavior, performance characteristics, etc)

4. Use the course dropbox (there is a link on the course homepage) to submit that tarball.

5. Schedule a live demo to present your system.