Distributed Algorithms (Winter 1997-8)

(Topics for Projects)

Hagit Attiya

Find an idea here or look in recent conferences ( PODC97, WDAG 97 and ICDCS 97) to find recent starting points. Then search the collected bibliographies or the Hypertext Bibliography Project to find related papers.
Here are some specifc ideas:
  1. The model of distributed computation presented by Java. Java (and its extensions) support at least synchronization issues, which are interesting from a theoretical viewpoint. Two possible points for investigation are:
    1. What is the power of synchrnization operations in Java. Can they solve wait-free consensus? Are they universal? To learn about the theoretical background you can start with Herlihy's "Universality" paper.
    2. What constraints are satisfied by shared memory accesses? The learn about the theoretical background you can start with Attiya and Welch.
  2. There are many algorithms for managing causal and total multicast, most of them in the context of group membership. Study simplified versions of these algorithms in the case groups are static, specify their properties and prove their correctness, also analyze their complexity. What happens when there are failures of various types?
  3. There are several definitions of virtual synchrony (start for example with [Fekete, Lynch and Shvartsman, PODC 97]). State them all (precisely) in a single framework, show relationships between them (in the form of reductions, separations, etc.), and/or study their "power".
  4. An operational proof for the fast mutual exclusion algorithm (Lamport) and its extensions (Yang and Anderson).
  5. Other stuff on synchronization structures.
  6. Read [Attiya and Dagan, PODC 96], [Afek, Merritt, Taubenfeld and Touitou, PODC 97], and
    1. Present resource allocation and algorithms for sensitive implementations of objects
    2. Also prove relations between the definitions.
    3. Can these works be extended using Afek, Dauber and Touitou.
  7. Extend the proof of 2-set consensus to general k (with f=n-1).
  8. Extend the algorithm from Chapter 5 to general number of simulating processors (use snapshots).
  9. Complete the details for the iterated immediate snapshots simulation of read and write [Borowski and Gafni, PODC 97].
  10. Byzantine quorum systems [Malkhi, Reiter and Wool, PODC 97], [Bazzi, PODC 97], and [Malkhi, Reiter and Wright, PODC 97].
  11. The consensus hierarchy classifies objects according to their ability to solve consensus ([Ruppert, PODC 97], [Lo and Hadzilacos, PODC 97]).
  12. Self-stabilization.
  13. Check pointing. See also [Alvisi and Marzullo, PODC 96].
  14. Failure detectors.
  15. Routing. See also [Gavoille and Perennes, PODC 96].
  16. Algorithms for mutual exclusion that take into consideration the architeture [Mellor-Crummey and Scott].
  17. Clock synchronization is an important topic. Start with [Patt-Shamir and Rajsbaum, STOC 94] and either:
    1. find more fault-tolerant algorithms; or
    2. extend to internal clock synchronization (perhaps not optimal); or
    3. show a modular use of approximate agreement; prove bounds on the number of messages or the distance of communication, or the length of dependency chains.
    4. specialize the algorithms for specific interesting graphs (regular? compact?).