Distributed Algorithms (Winter 2000-1)

Projects' Ideas

Hagit Attiya

Find an idea here or look in recent conferences (PODC, DISC and other conferences) to find recent starting points.
For additional papers, search the Research Index , the DB & LP bibliography , or the Hypertext Bibliography Project .

Contact me if you have other ideas you want to explore and develop.

Please check this page again: Additional ideas or pointers might be added

Here are some specifc ideas:
  1. The model of distributed computation presented by Java. 
    Java (and its extensions) several synchronization mechanisms, 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 from the course's textbook.
  2. 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".
  3. Group communication (De Prisco, et al., PODC 98; Chockler et al., PODC 98)
  4. Find an operational proof for the fast mutual exclusion algorithm (Lamport) and its extensions (Yang and Anderson, Anderson and Kim).
  5. 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]?
  6. Synchronization primitives for practical machines (Moir, PODC 97 and PODC 00; Anderson et al., PODC 97).
    See also this page, describing work done at Sun.
  7. Byzantine quorum systems [Malkhi, Reiter and Wool, PODC 97], [Bazzi, PODC 97], and [Malkhi, Reiter and Wright, PODC 97].
  8. The consensus hierarchy classifies objects according to their ability to solve consensus ([Ruppert, PODC 97], [Lo and Hadzilacos, PODC 97]).
  9. Compact routing (session 1 of PODC 00)
  10. Competitive algorithms for object replication (Johnson and Singh, PODC 00)
  11. Group mutual exclusion (Joung, PODC 98)
  12. Distributed data structures (Shavit and Zemach, PODC 98)
  13. Failure detectors (Mostefaoui and Raynal, PODC 00; Yang et al., PODC 98)
  14. Check pointing. See also [Alvisi and Marzullo, PODC 96].
  15. Algorithms for mutual exclusion that take the architeture into consideration [Mellor-Crummey and Scott].
  16. 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?).
    See also a recent paper by [Kutten and Patt-Shamir].