Spring 2014

The exam will primarily focus on material since Exam 1, although there may be references to earlier material. Review the following:

- Lectures through Fri, Mar 28, plus Wed, Apr 2.
Powerpoint slides are available online.
- Readings from textbook:
- Chapter 5; skip 5.3.2
- Chapter 14; skip 14.2, 14.3.3, and 14.3.4
- Chapter 6; skip 6.2.2
- Chapter 13; skip 13.3 and 13.4
- Chapter 7
- Chapter 8; skip 8.3 and 8.4
- Chapter 9

- Homeworks 3 and 4 and their solutions (gone over in class), including the assigned papers.

The format of the exam will be some short answers and some "work-out" problems. Here are some suggestions for things to know:

- crash-resilient consensus algorithm
- f+1 rounds lower bound for crash-resilient consensus
- n > 3f processor lower bound for Byzantine-resilient consensus
- exponential consensus algorithm for Byzantine failures
- phase-king algorithm for Byzantine failures
- wait-free impossibility of consensus in asynchronous shared memory; extensions to 1-resilient shared memory and message passing
- randomized asynchronous crash-resilient consensus algorithm using get-core and common-coin
- happens-before relation
- logical clocks algorithm
- vector clocks algorithm and lower bound on size of vector
- consistent cuts and applications
- clock synchronization algorithm for failure-free no-drift case and matching lower bound on clock skew
- n > 3f processor lower bound for Byzantine-resilient clock synchronization and matching algorithm
- specification of basic broadcast and how to implement it on top of point-to-point message passing
- specification of single-source FIFO broadcast and how to implement it on top of basic broadcast (add sequence numbers)
- specification of totally-ordered broadcast and how to implement it on top of basic broadcast (central server) and on top of SSF broadcast (Algorithm 21)
- specification of causal broadcast and how to implement it on top of basic broadcast (Algorithm 22)
- specification of reliable broadcast and how to implement it on top of basic broadcast (flooding, Algorithm 23)
- definitions of linearizable and sequentially consistent distributed shared memory
- algorithm to implement linearizable register (use totally-ordered broadcast for both reads and writes)
- two algorithms to implement sequentially consistent register (use totally-ordered broadcast just for writes or just for reads)
- lower bound of d on sum of read time and write time for sequential consistency
- lower bound of u/2 on write time for linearizability
- lower bound of u/4 on read time for linearizability