CS:5620 Distributed Systems and Algorithms
Spring 2016
12:301:45 TTh Room 75 SH (Schaeffer Hall)
Instructor:
Sriram V. Pemmaraju
101G MLH, srirampemmaraju@uiowa.edu, 3193532956
Office Hours: 1:302:30 M, 10:3011:30 W, 2:003:00 F (and by appointment)
Course website: http://www.cs.uiowa.edu/~sriram/5620/fall16/
Department website: http://www.cs.uiowa.edu/
Modern life is increasingly dependent on networked services such as web searching, ecommerce, videoconferencing,
stock trading and net banking, social media, video streaming, etc.
Networks of sensors provide a variety of specialized services such as testing integrity of bridges, assessing nutrient content
of farm soil, etc., whereas networks of mobile devices are being used for tasks such as gathering realtime blood pressure readings
from patients, providing healthrelated alerts, etc.
Also, with the increasing need to quickly process massive amounts of data, distributed systems are playing a
key role in "big data" analytics.
While physical networks provide the underlying connectivity, various services built on top of these networks are
examples of distributed systems.
The objective of this course is to study some of the foundational issues that arise in the design of distributed systems
(but which may be absent in centralized or sequential systems).
These issues include
computing with local or partial knowledge,
faults and designing faulttolerant systems,
asynchrony and the cost of simulating synchrony,
randomization versus determinism in distributed settings,
achieving parallelism
and
tradeoffs between communication and computation.
A tentative list of specific topics that we will cover in this course are:
 The Distributed Graph Coloring Problem.
 The ColeVishkin Deterministic Distributed Graph Coloring Algorithm.
 Linial's Lower Bound on Distributed Graph Coloring.
 Luby's Randomized Graph Coloring and Maximal Independent Set Algorithms
 Leader Election in Rings: Synchronous and Asynchronous Settings
 Low Message Complexity Leader Election in a Clique
 Minimum Spanning Trees (MST): the GallagherHumbletSpira Algorithm and the PelegKutten Algorithm
 Introduction to Communication Complexity and Lower Bounds for MST
 Time, Causality, and Clock Synchronization
 Simulating Synchrony: Implementing Synchronizers
 Distributed Snapshots
 Faulttolerant Consensus
 Mutual Exclusion
Syllabus document,
Information about TAs,
Announcements,
Quizzes, Projects, and Exams,
Weekly Topics,
Online Resources
My 4th year PhD student, Talal Riaz is the TA for this course. Talal's office hours
are from 10:30 to noon on Tuesdays and Thursdays in 101N, MLH. Talal can be reached via
email at talalriaz@uiowa.edu.

Week 1: 8/228/26
Topics:
 The Distributed Graph Coloring problem.
 Introduction to the faultfree, synchronous, messagepassing model of distributed computing with unique IDs.
 The distributed greedy algorithm in this model for obtaining a (Delta+1)coloring for arbitrary graphs.
 The ColeVishkin technique of deterministic coin tossing.
Readings: Chapter 0 (Introduction) and Chapter 1 (Vertex Coloring) from
Professor Wattenhofer's notes. Chapter 1 (Introduction) and Chapter 2 (Model) from
Professor Pandurangan's notes. Handout on the LOCAL and CONGEST models.

Week 2: 8/299/2
Topics:
 Using the ColeVishkin approach to 3color oriented trees in O(log* n) rounds.
 Using the ColeVishkin approach to (Delta+1)color boundeddegree graphs in
O(log* n) rounds.
Readings: Chapter 0 (Introduction) and Chapter 1 (Vertex Coloring) from
Professor Wattenhofer's notes. Chapter 1 (Introduction) and Chapter 2 (Model) from
Professor Pandurangan's notes. Handout on the LOCAL and CONGEST models.

Week 3: 9/59/9
Topics:
 Introduction to randomized distributed algorithms.
 Luby's randomized algorithm for (Delta+1)coloring in O(log n) rounds. We will study the simplified version
and analysis due to Johansson.
Readings: Simple distributed Delta+1coloring of graphs.
For a review of discrete probability and random variables study Appendices C.2 and C.3 from
Introduction to Algorithms, 2nd ed., Cormen, Leiserson,
Rivest, and Stein.
Handout showing a "warmup" analysis of Luby's coloring algorithm.

Week 4: 9/129/16
Topics:
 Analysis of Luby's randomized MIS algorithm.
 Linial's Omega(log^* n) lower bound on 3coloring a directed cycle.
Readings:
Chapter 6 (Pages 6168) from Professor Pandurangan's notes.
Linial's Lower Bound Made Easy.

Week 5: 9/199/23
Topics:
 Linial's Omega(log^* n) lower bound on 3coloring a directed cycle.
 Simple treebased algorithms: flooding, BFStree construction, convergecast.
 Introduction to asynchronous algorithms.
 Distributed Dijkstra's algorithm and the BellmanFord algorithm.
Readings:
Chapter 2 from Professor Wattenhofer's notes.

Week 6: 9/269/30
Topics:
 Asynchronous BFS tree construction: Distributed Dijkstra's algorithm and the Distributed BellmanFord algorithm.
 The distributed minimum spanning tree problem.
 Distributed Kruskal's algorithm (aka the pipelined MST algorithm).

Readings:
Chapter 7 from Professor Pandurangan's notes.

Week 7: 10/310/7
Topics:
 The GallagherHumbletSpira (GHS) algorithm.
 The GarayKuttenPeleg algorithm.
Readings:
Chapter 7 from Professor Pandurangan's notes.

Week 8: 10/1010/14
Topics:
 Midterm
 Analyis of the GarayKuttenPeleg MST algorithm showing that it has round complexity O(sqrt{n}log^* n + diam(G)).
Readings:
Chapter 7 from Professor Pandurangan's notes.

Week 9: 10/1710/21
Topics:
 Analyis of the GarayKuttenPeleg MST algorithm showing that it has round complexity O(sqrt{n}log^* n + diam(G)).
 The Leader Election problem.
 Algorithms that have round complexity O(n) and message complexity O(n log n) on cycles in synchronous and
asynchronous settings.
Readings: Chapter 3 from Professor Wattenhofer's notes and
Chapter 5 from Professor Pandurangan's notes.

Week 10: 10/2410/28
Topics:
 A simple deterministic algorithm that solves the Leader Election (LE) problem on cycles in O(n) rounds using
O(n^2) messages.
 An improved deterministic algorithm that solves the Leader Election (LE) problem on cycles in O(n) rounds using
O(n log n) messages.
 A randomized algorithm that solves the Leader Election (LE) problem on cycles in O(n) rounds using
O(n log n) messages, in expectation.
 A deterministic algorithm that uses O(n) messages in the synchronous setting.
Readings: Chapter 3 from Professor Wattenhofer's notes and
Chapter 5 from Professor Pandurangan's notes.

Week 11: 10/3111/4
Topics:
 An Omega(n log n) lower bound on the message complexity of asynchronous LE algorithms on cycles.
 A lowmessage complexity LE algorithm on a clique: the use of the birthday paradox in the analysis. This algorithm runs in O(1) rounds (deterministically),
uses O(n^{1/2} (log n)^{3/2}) messages with high probability and is correct with high probability.
Readings: Chapter 3 from Professor Wattenhofer's notes and
Chapter 5 from Professor Pandurangan's notes.

Week 12: 11/711/11
Topics:
 Analysis of lowmessagecomplexity LE algorithm on a clique.
 The Distributed Replica Management problem in an asynchronous setting with message loss and node crashes.
 The 2 Phase Locking and 3 Phase Locking algorithms.
Readings: Chapter 15 on Faulttolerance and Paxos from Professor Wattenhofer's notes.

Week 13: 11/1411/18
Topics:
 Tolerating upto just under 50% nodes crashing: The Paxos algorithm of
Leslie Lamport.
Readings: Chapter 15 on Faulttolerance and Paxos from Professor Wattenhofer's notes.

Week 14: 11/2012/2
Topics:
 Proof of correctness of Paxos showing that it satisfies Validity and Agreement, but not necessarly
Termination.
 Introduction to the Distributed Consensus problem. The FischerLynchPatterson proof of
the impossibility of a deterministic solution to the Distributed Consensus problem that is tolerant
of even one crash.
Readings: Chapter 15 on Faulttolerance and Paxos and Chapter 16 on Consensus from Professor Wattenhofer's notes.

Week 15: 12/512/9
Topics:
 The FischerLynchPatterson proof ofthe impossibility of a deterministic solution to the Distributed Consensus problem that is tolerant
of even one crash.
 Ben Or's randomized algorithm for solving Distributed Consensus, tolerating f faults, for any f less
than n/2.
Readings: Chapter 16 on Consensus from Professor Wattenhofer's notes and these slides by Professor Lorenzo Alvisi on Ben Or's randomized algorithm for distributed consensus.