Topics in Distributed Computing

Fall 99 - EECS 594 (72135) Topics in Distributed Computing

Instructor: Ajay Kshemkalyani (ajayk@eecs.uic.edu)
Class meeting times: T,R 2:00-3:15pm
Room: DH 205
Office Hours: (M 2:00PM - 2:50PM; T,W 12:00PM - 12:50PM)@915 SEO
URL: http://www.eecs.uic.edu/~ajayk/ext/dc594.html

Course Description (very tentative)

Reliable group communication, Managing group views
I/O automata; Timed and untimed automata
Distributed shared memory - models and implementations
Synchronous network algorithms
Asynchronous shared memory and network algorithms
Atomic registers, Composite registers, Atomic objects
Distributed predicates and predicate detection; Distributed debugging
Checkpointing and rollback recovery
Counting networks
Agreement and consensus; randomized consensus; Survivable consensus objects
Failure detectors
Wait-free synchronization, Wait-free hierarchy
Network synchronizers
Other current topics

Prerequisites

Algorithm analysis and design, Operating systems, Computer networks, Permission of the instructor.

Course Requirements

In addition to the class textbooks, a collection of recent research articles will be made available. This course focuses on theoretical principles. You will not learn any programming in this course.

The course format will be in two parts. For the first part, the instructor will teach some basic topics. The second part involves active student participation and is tentatively planned as follows. Students will be required to present 2 topics. Each topic will entail presenting material from multiple papers, and/or multiple chapters from the books. Students are required to lead the discussion of the topics assigned to them. Depending on the class size, the presentations of the topics/papers can be done in teams. Each student also has to critique the various papers/chapters, and participate in class discussions. Everyone is expected to submit in advance a 1-page critique/review of the topic assigned for the class, for every class in the second part of the course. For details on how to structure the critique, see below.

There will be one or more exams. In addition, a term paper will be required of each student -- original content is expected.

(Tentative) Grading: Reviews/Critiques 25%; Presentation 15%; Exam(s) 30%; Term paper 30%. Grading is relative. The full scale of grades will be used. Handwritten submissions, except for the exam(s), will likely not be accepted.

TAKE-HOME EXAM ASSIGNED ON DEC 2 at 3:30 PM. DUE BACK ON DEC 4 at 5:00 PM.

Class Participation

The success of this class depends on a high degree of participation in class discussions. To facilitate active participation, students are expected to read and critique the assigned chapters or papers in advance of the class discussion. At the beginning of each class, students must turn in a short review of the chapters or papers to be discussed. The review should: (i) summarize the main points of the chapter/paper, (ii) list important conclusions of the chapter/paper, and (iii) list any deficiencies that you found, and directions for future improvements, and (iv) list at least three intelligent questions to be asked to the presenter. Each review should be short and crisp.

Reading List

(Primary:) Distributed Computing by Attiya and Welch, McGraw Hill, 1998
(Primary:) Distributed Operating Systems by Singhal and Shivaratri, McGraw Hill, 1994
Selected papers from the literature.
1. Distributed spanning tree algorithms
  - R.G. Gallager, P.A. Humblet, and P.M. Spira. "A Distributed Algorithm for Minimum-Weight Spanning Trees," ACM Transactions on Programming Languages and Systems, 5(1):66-77, January 1983.
  - B. Awerbuch. "Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems," Proc. 19th Symp. on Theory of Computing, pp. 230-240, May 1987.
  - M. Faloutsos, and M. Molle. "Optimal Distributed Algorithms for Minimum Spanning Trees Revisited," 14th ACM Symp. on Principles of Distributed Computing (PODC'95). Ottawa, Ontario. August 1995.
2. Fast mutual exclusion algorithms for shared memory
  - R. Alur, G. Taubenfeld, "Fast timing based algorithms," Distributed Computing, 10(1): 1-10, 1996. Follow this link
  - L. Lamport, "A fast mutual exclusion algorithm," ACM Transactions on Computer Systems, 5(1): 1-11, 1987.
3. Detection of unstable predicates
  - V. Garg, B. Waldecker, "Detection of weak unstable predicates in distributed programs", IEEE Transactions on Parallel and Distributed Systems, 5(3):299-307, 1994. Follow this link
  - V. K. Garg, B. Waldecker, ``Detection of Strong Unstable Predicates in Distributed Programs,'' IEEE Transactions on Parallel and Distributed Systems, 7(12):1323-1333, 1996. Follow this link
  - C. Chase, V. Garg, "Detection of global predicates: Techniques and their limitations," Distributed Computing, 11(4): 191-201, 1998. Follow this link
  - S. Stoller, L. Unnikrishnan, Y. Liu, "Efficient detection of global properties in distributed systems using partial-order methods," Tech Report 523, Indiana University, Sept. 1999.
4. Dimension-bound analysis for efficient vector clocks
  - P. Ward, "An online algorithm for dimension-bound analysis," Proceedings of Euro-Par'99, 144-153, LNCS 1685, September 1999.
  - P. Ward, "An offline algorithm for dimension-bound analysis," Proceedings of ICPP'99, September 1999.
5. Inhibition spectrum
  - C. Critchlow, K. Taylor, The inhibition spectrum and the achievement of causal consistency, Distributed Computing, 10(1): 11-27, 1996. Follow this link
6. Wait-free synchronization
  - M. Herlihy, "Wait-free synchronization," ACM Transactions on Programming Languages and Systems, 11(1): 124-149, Jan 1991.
  - P. Jayanti, "On the robustness of Herlihy's hierarchy," 12th ACM Symp. on Principles of Distributed Computing, 145-157, 1993.
7. Failure detectors (2 presentations)
  - E. Fromentin, M. Raynal, F. Tronel, "About Classes of Problems in Asynchronous Distributed Systems with Process Crashes," 19th IEEE International Conference on Distributed Computing Systems, 470-477, May 1999. Follow this link
  - A. Schiper, Early consensus in an asynchronous system with a weak failure detector, Distributed Computing, 10(3): 149-157, 1997. Follow this link
8. Multiprocessor synchronization (3 presentations)
  - J. Anderson and J.-H. Yang, "Time/Contention Tradeoffs for Multiprocessor Synchronization", Information and Computation , Vol. 124, No. 1, pp. 68-84, January 1996. Follow this link
  - James H. Anderson and Mark Moir, "Using Local-Spin k-Exclusion Algorithms to Improve Wait-Free Object Implementations," Distributed Computing 11(1), 1997. Follow this link
  - Mark Moir, "Efficient Object Sharing in Shared-Memory Multiprocessors," Ph.D. Thesis, University of North Carolina at Chapel Hill, 1996. Follow this link
  - J. Anderson and M. Moir, "Universal Constructions for Large Objects," to appear in IEEE Transactions on Parallel and Distributed Systems. Follow this link
9. Composite registers
  - J. Anderson, "Composite Registers", Distributed Computing, 6(3):141-154, April 1993. Follow this link
10. Implementations of distributed shared memory
  - Check out web pages such as the following. link, link, link, link

Presentations

Four weeks before your presentation, you must be give me a clean copy of the paper you will be presenting. This will be distributed to the class at least 3 weeks before the presentation date. You have at least three weeks to study and critique all the papers (except your own). The following is the schedule of presenters and dates of presentations.

October 26: (PM) Minimum Spanning Trees
October 28: (AB) Fast Mutual Exclusion
November 2: (DV) Predicate detection
November 4: (NG) DSM implementations
November 9: (RR) Inhibition spectrum
November 11: (JS) Failure detectors
November 16: (AR) Faliure Detectors
November 18: (SB) Wait-free hierarchy (textbook)
November 23: (RS) Universal Constructins for Large Objects
November 30: (LH) Algorithms for Dimension-bound analysis
December 2: (NS) Composite registers