CS:5620 Distributed Systems and Algorithms
Spring 2016

Instructor:
Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3: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, e-commerce, video-conferencing, 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 real-time blood pressure readings from patients, providing health-related 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 fault-tolerant systems, asynchrony and the cost of simulating synchrony, randomization versus determinism in distributed settings, achieving parallelism and trade-offs between communication and computation. A tentative list of specific topics that we will cover in this course are:

• The Distributed Graph Coloring Problem.
• The Cole-Vishkin 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 Gallagher-Humblet-Spira Algorithm and the Peleg-Kutten Algorithm
• Introduction to Communication Complexity and Lower Bounds for MST
• Time, Causality, and Clock Synchronization
• Simulating Synchrony: Implementing Synchronizers
• Distributed Snapshots
• Fault-tolerant Consensus
• Mutual Exclusion

Syllabus document, Information about TAs, Announcements, Quizzes, Projects, and Exams, Weekly Topics, Online Resources

Information about TAs

Homeworks and Exams

• Homework 1. Due in class on Thu, 9/8. Homework 1 Solution.
• Homework 2. Due in class on Thu, 9/22. Homework 2 Solution.
• Homework 3. Due in class on Tue, 10/11. Homework 3 Solution.
• Homework 4. Due in class on Thu, 10/27. Homework 4 Solution.
• Midterm and Solution to midterm.
• Homework 5. Due in class on Tue, 11/29.
• Midterm Retake.

Announcements

• 8/29: I will be out of town on Friday, Sept 2nd and will not be holding office hours on that day.
• 9/12: I will be out of town in the afternoon tomorrow (Tuesday, 9/13). The class TA, Talal Riaz will lecture on my behalf.
• 9/20: The midterm will be on Tue, Oct 11th in 105 SSH from 6:30pm to 8:30pm. More details will appear here a few days before the exam.
• 10/4: Here is some information about the upcoming midterm exam.
• 10/4: I will not be at office hours on Wednesday, 10/5. I will have "make-up" office hours on Thursday, 10/6, just before class from 11:15 am to 12:15 pm.

Weekly Topics

• Week 1: 8/22-8/26
  Topics:
  • The Distributed Graph Coloring problem.
  • Introduction to the fault-free, synchronous, message-passing model of distributed computing with unique IDs.
  • The distributed greedy algorithm in this model for obtaining a (Delta+1)-coloring for arbitrary graphs.
  • The Cole-Vishkin 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/29-9/2
  Topics:
  • Using the Cole-Vishkin approach to 3-color oriented trees in O(log* n) rounds.
  • Using the Cole-Vishkin approach to (Delta+1)-color bounded-degree 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/5-9/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+1-coloring 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 "warm-up" analysis of Luby's coloring algorithm.

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

• Week 5: 9/19-9/23
  Topics:
  • Linial's Omega(log^* n) lower bound on 3-coloring a directed cycle.
  • Simple tree-based algorithms: flooding, BFS-tree construction, convergecast.
  • Introduction to asynchronous algorithms.
  • Distributed Dijkstra's algorithm and the Bellman-Ford algorithm.
  Readings: Chapter 2 from Professor Wattenhofer's notes.

• Week 6: 9/26-9/30
  Topics:
  • Asynchronous BFS tree construction: Distributed Dijkstra's algorithm and the Distributed Bellman-Ford 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/3-10/7
  Topics:
  • The Gallagher-Humblet-Spira (GHS) algorithm.
  • The Garay-Kutten-Peleg algorithm.
  Readings: Chapter 7 from Professor Pandurangan's notes.

• Week 8: 10/10-10/14
  Topics:
  • Mid-term
  • Analyis of the Garay-Kutten-Peleg 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/17-10/21
  Topics:
  • Analyis of the Garay-Kutten-Peleg 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/24-10/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/31-11/4
  Topics:
  • An Omega(n log n) lower bound on the message complexity of asynchronous LE algorithms on cycles.
  • A low-message 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/7-11/11
  Topics:
  • Analysis of low-message-complexity 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 Fault-tolerance and Paxos from Professor Wattenhofer's notes.

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

• Week 14: 11/20-12/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 Fischer-Lynch-Patterson proof of the impossibility of a deterministic solution to the Distributed Consensus problem that is tolerant of even one crash.
  Readings: Chapter 15 on Fault-tolerance and Paxos and Chapter 16 on Consensus from Professor Wattenhofer's notes.

• Week 15: 12/5-12/9
  Topics:
  • The Fischer-Lynch-Patterson 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.