Assignment 4

Due Wednesday, October 19, 2016 6:55pm 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.

There are two documents to read (about 16 pages in total) and a half hour of video to watch. Make sure you allocate sufficient time.

Reading

Virtual Synchrony
Ken Birman, A History of the Virtual Synchrony Replication Model, 2010.
Read at least pages 1-7. This document is by the creator of virtual synchrony and provides an overview of what it was designed to do and how it works.
Virtual Synchrony, Wikipedia article
[approximately 9 pages]
The wikipedia article is concise and does a decent job in outlining the basic principles of virtual synchrony.

Watching

Paxos
Implementing Replicated Logs with Paxos, March 1, 2013
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 strongly recommend that you watch the video through to the end. 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.

Questions

  1. Why does Isis virtual synchrony depend on a failure detection service within the Group Management Service instead of just having individual processes detect failures via timeouts?
  2. What causes a view change in virtual synchrony?
  3. Why can an acceptor not necessarily accept the first value it receives but must sometimes accept different values?
  4. When does a proposer have to change the value that it is proposing during the Paxos consensus protocol?