CS:5620 Distributed Systems and Algorithms
Fall 2020

Instructor:
Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Virtual 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/fall20/
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:

• Introduction to distributed computing models and algorithmic ideas via the distributed graph coloring problem.
  • The Cole-Vishkin deterministic distributed graph coloring algorithm.
  • Linial's lower bound for distributed graph coloring.
• Introduction to randomized distributed algorithms.
  • Luby's randomized maximal independent set algorithm
  • Johnson's randomized graph coloring algorithm
• Tree-based algorithms.
  • Distributed BFS, flooding, Distributed Dijkstra and Bellman-Ford shortest path algorithms
  • Minimum Spanning Trees (MST): the Gallagher-Humblet-Spira Algorithm and the Peleg-Kutten Algorithm
• Distributed computing lower bounds via communication complexity
  • The 2-party communication model, problems and simple upper and lower bounds
  • Lower Bounds for MST via 2-party SetDisjointness
• Fault-tolerant Consensus
  • The Paxos algorithm
  • The Fischer-Lynch-Patterson proof of impossibility of deterministic fault-tolerant consensus
  • Ben-Or's randomized algorithm for fault-tolerant consensus
• Distributed ``big data'' algorithms
  • A model of computation for MapReduce by Karloff et al.
  • Filtering: a method for solving graph problems in MapReduce by Lattanzi et al.
  • Improved Massively Parallel Computation Algorithms for Maximal Independent Sets.

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