CSE 6117, Winter 2023
CSE 6117
Theory of Distributed Computing
Winter 2023
Instructor: Eric Ruppert
Office: Lassonde Building, room 3052
Email: [my last name] @eecs.yorku.ca
Telephone: (416) 736-2100 ext. 33948
Lectures: Mondays 10:00-11:30 in room 203 of Stong College and Wednesdays 10:00-11:30 in room 318 of Calumet College
Office Hours: Mondays 16:10-17:00 and Wednesdays 11:40-12:30 in Lassonde 3052.
Usually, the best way to contact me is by email. Please use a York account when sending me email, and start your subject line with "[6117]".
Announcements
- (Mar 29) Please fill out a course evaluation at this link until April 11. If more than 80 per cent of the class fill them out, I will drop your lowest assignment when computing final grades.
- (Jan 23) My office hour on Wed, Jan 25 will be cancelled. Instead, I will be available on Thu, Jan 27 from 12:00 to 13:00.
Course Description
Can a given problem be solved in a distributed system? If so, how
efficiently can it be solved? We investigate how the answers to these
questions depend on aspects of the underlying distributed system
including synchrony, fault-tolerance and the means of communication
between processes.
A tentative list of topics:
- shared-memory and message-passing models of distributed systems,
- mutual exclusion,
- agreement problems (consensus, leader-election, Byzantine agreement, approximate agreement),
- broadcast and multicast algorithms,
- impossibility results and lower bounds,
- the consensus hierarchy,
- implementing shared data structures,
- randomization in distributed computing,
- self-stabilization, and
- a theoretical model for mobile computing.
Marking scheme
| Homework exercises | 70% |
| Presentation | 20% |
| Participation | 10% |
See this link for information about the presentations.
Important Dates
| First class | Monday, January 9 |
| Reading week | February 20-24 |
| Last day to drop course without receiving a grade
| Monday, March 13 |
| Last class | Wednesday, April 5 |
Lectures
These will be filled in as the term progresses.
The references below are intended for students who want to read more about the topics discussed in class. Sometimes the readings might be helpful for the assignments. Sometimes they will extend the ideas covered in lectures.
- January 9: Introduction describing what the course is about. 2 generals problem.
- January 11: Dijkstra's mutual exclusion algorithm. [Dij65], some notes
- January 16: Comparing models of distributed computing.
- January 18: Broadcasting and building a spanning tree (flooding), minimum spanning tree [GHS83 or Lyn96, Chapter 15.5]
- January 23: Leader election [AW04, chapter 3]
- January 25: Leader election, continued
- January 30: Colouring a network [Suo20, chapter 1]
- February 1: Consensus in synchronous network with crash failures: algorithm and lower bound [AW04, chapter 5.1]
- February 6,8: Consensus in synchronous network with Byzantine failures [AW04, section 5.2] or [Lyn 96, chapter 6]
- February 13: Reliable broadcast, approximate agreement [ST87, AAD04]
- February 15: Impossibility of consensus using read-write registers [FLP85, AW04 section 5.3, Her91]
- March 1: Consensus using fetch-and-increment or stacks [Her91]
- March 3: Consensus hierarchy [AW04 section 15.2], linearizability [HW90, HSLS20 chapter 3], counters
- March 6: Snapshot objects [AADGMS93]
- March 8: Lock-free queues [MS98, HSLS20 chapter 10]
- March 13: Universal Construction [Her91, HSLS20 chapter 6, AW04 section 15.3]]
- March 15: Lock-free BST [EFRV10]
- March 20: A lock-free hashing scheme [HSLS20 section 13.3, SS06]
- March 22: Renaming [AW04 section 16.3, MA95]
- March 27: Presentations by
Elim (anonymous mutual exclusion)
Suyash (a different lock-free BST)
- March 29: Presentations by
Xingjian (payment channels in asynchronous money transfer systems ),
Kuimou (multiplying sparse matrices in parallel)
- April 3: Presentations by
Fares (load-balancing in P2P systems),
Wejdene (hedging against sore loser attacks in cross-chain transactions),
Amirreza (scaling byzantine agreement for cryptocurrencies ),
- April 5: Presentations by
Amirhossein (faster leader election),
Ali (differential privacy of gossip protocols),
Mohammadhossein (round-efficient Byzantine agreement)
References
There is no required textbook for the course. However, I shall sometimes recommend readings from books or papers. These references will be listed here, and the list will grow during the term. Accessing some of the links below may require you to be logged into a machine at York, so that you can access the ACM Digital Library, etc.
Books
- [AE14] Hagit Attiya and Faith Ellen. Impossibility Results for Distributed Computing. Morgan & Claypool, 2014.
- [AW04] Hagit Attiya and Jennifer Welch. Distributed Computing:
Fundamentals, Simulations and Advanced Topics, 2nd edition. Wiley, 2004.
- [GK18] Rachid Guerraoui and Petr Kuznetsov. Algorithms for Concurrent Systems. EPFL Press, 2018.
- [HSLS20] Maurice Herlihy, Nir Shavit, Victor Luchangco and Michael Spear. The Art of Multiprocessor Programming, 2nd ed. Morgan Kaufmann, 2020.
- [Lyn96] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
- [Suo20] Jukka Suomela. Distributed Algorithms 2020
- [Tau06] Gadi Taubenfeld. Synchronization Algorithms and Concurrent Programming. Pearson Education, 2006.
Papers
- [AAD04] Ittai Abraham, Yonatan Amit and Danny Dolev. Optimal resilience asynchronous approximate agreement. In Proc. International Conference on Principles of Distributed Systems, pages 229-239, 2004.
- [AADGMS93] Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt and Nir Shavit. Atomic snapshots of shared memory. J. of the ACM, 40(4), pages 873-890, September 1993.
- [EFRV10] Faith Ellen, Panagiota Fatourou, Eric Ruppert and Franck van Breugel. Non-blocking Binary Search Trees. In Proc. 29th ACM Symposium on Principles of Distributed Computing, pages 131-140, 2010.
- [FLP85] Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), pages 374-382, April 1985.
- [GHS83] R. G. Gallager, P. A. Humblet and P. M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and System Sciences, 5(1), pages 66-77, 1983.
- [Her91] Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1), pages 124-149, January 1991.
- [HW90] Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3), pages 463-492, July 1990.
- [MS98] Maged M. Michael and Michael L. Scott. Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing, 51(1):1-26, 1998.
- [MA95] Mark Moir and James H. Anderson. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming 25(1):1-39, 1995.
- [SS06] Ori Shalev and Nir Shavit. Split-ordered lists: lock-free extensible hash tables. Journal of the ACM 53(3):379-405, 2006.
- [ST87] T.K. Srikanth and S. Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing 2(2):80-94, 1987.
Web Pages
Previous version of this course:
Fall 2016.
Exercises
Try to keep your answers as simple as possible (but no simpler).
Important note on collaboration on homework assignments: It is okay to discuss the general approach to solving a problem with your classmates. However, you should not take any written notes away from such a discussion, and you should write up your solution on your own. Also, to protect yourself against charges of plagiarism, you should write on the front page of your assignment the names of any classmates that you discussed the problem with, and any outside sources that you used.
This page was last updated on April 3, 2023