Computing with infinitely many processes

We explore four classic problems in concurrent computing (election, mutual exclusion, consensus, and naming) when the number of processes which may participate is unbounded. Partial information about the number of processes actually participating and the concurrency level is shown to affect the computability and complexity of solving these problems when using only atomic registers. We survey and generalize work carried out in models with known bounds on the number of processes, and prove several new results. These include improved bounds for election when participation is required and a new adaptive starvation-free mutual exclusion algorithm for unbounded concurrency. We also survey results in models with shared objects stronger than atomic registers, such as test&set bits, semaphores or read–modify–write registers, and update them for the unbounded case.

Authors

• Michael Merritt
• Gadi Taubenfeld

Keywords

• Infinitely many processes
• Bounded concurrency
• Unbounded concurrency
• Election
• Mutual exclusion
• Consensus
• Naming