What Can Be Implemented Anonymously?
Here's another interesting paper in distributed computing that I read recently: "What Can be Implemented Anonymously?" by Geurraoui and Ruppert in DISC 2005.
Lots of the classic distributed algorithms require every process to have (and use) a unique identifier; this makes some problems easy to solve. The paper asks which problems can be solved, in a shared-memory model, without such IDs, and gives good answers. Of course, this anonymity is a technical one and is quite different from the notion of personal privacy, but the existence of such anonymous algorithms might facilitate some real applications that offer such privacy.
First they implement an object called a weak counter, which returns non-decreasing numbers over time, and they use this to implement the other algorithms in the paper. Then they give good efficient for consensus and snapshot and give space complexity bounds for their algorithms. Finally, they characterize the distributed objects that can be implemented anonymously: every idempotent object is implementable. All of the implementations are wait-free, non-blocking, or obstruction-free.
The paper is a brisk and readable 14 pages and has good, clear arguments of correctness.