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:
- 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:- 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. - What constraints are satisfied by shared memory accesses?
The learn about the theoretical background you can start with from the course’s textbook.
- What is the power of synchrnization operations in Java.
- 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”.
- Group communication (De Prisco, et al., PODC 98; Chockler et al., PODC 98)
- Find an operational proof for the fast mutual exclusion algorithm (Lamport) and its extensions (Yang and Anderson, Anderson and Kim).
- Read [Attiya and Dagan, PODC 96], [Afek, Merritt, Taubenfeld and Touitou, PODC 97], and
- Present resource allocation and algorithms for sensitive implementations of objects
- Also prove relations between the definitions.
- Can these works be extended using [Afek, Dauber and Touitou]?
- 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. - Byzantine quorum systems [Malkhi, Reiter and Wool, PODC 97], [Bazzi, PODC 97], and [Malkhi, Reiter and Wright, PODC 97].
- The consensus hierarchy classifies objects according to their ability to solve consensus ([Ruppert, PODC 97], [Lo and Hadzilacos, PODC 97]).
- Compact routing (session 1 of PODC 00)
- Competitive algorithms for object replication (Johnson and Singh, PODC 00)
- Group mutual exclusion (Joung, PODC 98)
- Distributed data structures (Shavit and Zemach, PODC 98)
- Failure detectors (Mostefaoui and Raynal, PODC 00; Yang et al., PODC 98)
- Check pointing. See also [Alvisi and Marzullo, PODC 96].
- Algorithms for mutual exclusion that take the architeture into consideration [Mellor-Crummey and Scott].
- Clock synchronization is an important topic. Start with [Patt-Shamir and Rajsbaum, STOC 94] and either:
- find more fault-tolerant algorithms; or
- extend to internal clock synchronization (perhaps not optimal); or
- 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.
- specialize the algorithms for specific interesting graphs (regular? compact?).
See also a recent paper by [Kutten and Patt-Shamir].