Assignment 3

Due Wednesday October 18, 2017 via sakai

Introduction

Please answer the questions precisely and concisely. Every question can be answered in one or at most a few sentences. I will not have the patience to read long paragraphs or essays and you may lose credit for possibly correct answers.

Note: submissions must be be plain text or pdf files or HTML within sakai. Other formats, such as Microsoft Word, Apple Pages, or Adobe InDesign will not be accepted.

Topic

Your assignent comprises two parts:

  • Watch a video that discusses how the Paxos consensus protocol works and deals with certain failures.

  • Read about the RAFT consensus protocol. This was created at Stanford University as an alternative to Paxos, with the primary goal of creating a protocol that is easier to understand than Paxos.

Watching

John Ousterhout and Diego Ongaro, Implementing Replicated Logs with Paxos, Stanford University, 2014

This video presentation by John Ousterhout is one of the clearest explanations I could find on Paxos. Although its purpose is to use Paxos to create replicated logs, the first part is a generic introduction to Paxos with a discussion of how it achieves fault-tolerant consensus. The replicated log problem applies to many other replicated state machines.

The fundamental algorithm, Basic Paxos, is explained from the start through to 31:50, but I recommend that you watch the video through to the end to get a feel for the algorithm.

Note that there’s a blackout from 17:08 through 17:29 but stay with it since the step-by-step sequence of Paxos is described right after that.

Reading

Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm, Stanford University, 2014
Raft was designed as a consensus protocol that is equivalent to Paxos in fault-tolerance and performance but it easier to understand.
Read at least pages 1–9 if you don’t feel like reading the entire 16 page document.
Raft interactive tutorial at The Secret Lives of Data.
Allocate at least five minutes of time for this.

Questions

Question 1

Why can an acceptor not necessarily accept the first value it receives but must sometimes accept different values?

Question 2

When does a proposer have to change the value that it is proposing during the Paxos consensus protocol?

Question 3

Raft uses a single leader (one server is elected as a leader). Explain how Raft performs leader election.

Question 4

An elected leader takes client requests. Each request is essentially a log entry that will be replicated among the servers. When is a log entry committed in Raft?