A pleasant stroll through the land of infinitely many creatures
Author:
Open Access
- 1 June 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 35 (2) , 36-59
Abstract
Many distributed algorithms are designed for a system with a fixed set of n processes. However, some systems may dynamically change and expand over time,so that the number of processes may grow to infinity as time tends to infinity. This paper considers such systems, and gives algorithms that are new and simple (but not necessarily efficient) for common problems. The reason for simplicity is to better expose some of the algorithmic techniques for dealing with infinitely many processes. A brief summary of existing work in the subject is also provided.Keywords
This publication has 33 references indexed in Scilit:
- Algorithms adapting to point contentionJournal of the ACM, 2003
- Deconstructing paxosACM SIGACT News, 2003
- The topological structure of asynchronous computabilityJournal of the ACM, 1999
- Fault-tolerant wait-free shared objectsJournal of the ACM, 1998
- Computing with faulty shared objectsJournal of the ACM, 1995
- Wait-free algorithms for fast, long-lived renamingScience of Computer Programming, 1995
- Atomic snapshots of shared memoryJournal of the ACM, 1993
- On interprocess communicationDistributed Computing, 1986
- On interprocess communicationDistributed Computing, 1986
- Solution of a problem in concurrent programming controlCommunications of the ACM, 1965