Journal article

From wait-free to arbitrary concurrent solo executions in colorless distributed computing

In an asynchronous distributed system where any number of processes may crash, a process may have to run solo, computing its local output without receiving any information from other processes. In the basic shared memory system where the processes communicate through atomic read/write registers, at most one process may run solo. This paper introduces the family of d-solo models, where d-processes may concurrently run solo, 1 <= d <= n (the 1-solo model is the basic read/write model). The paper then studies distributed colorless computations in the d-solo models, where process ids are not used, either in task specifications or during computation. It presents a characterization of the colorless tasks that can be solved in each d-solo model. Colorless tasks include consensus, set agreement and many other previously studied tasks. It shows that colorless algorithms have limited computational power for solving tasks, only when d > 1. When d = 1, colorless algorithms can solve the same tasks as algorithms that may use ids. It is well-known that, while consensus is not wait-free solvable in a model where at most one process may run solo, epsilon-approximate agreement is solvable. In a d-solo model, the fundamental solvable task is (d, epsilon)-solo approximate agreement, a generalization of epsilon-approximate agreement. Indeed, (d, epsilon) -solo approximate agreement can be solved in the d -solo model, but not in the (d + 1) -solo model. Finally, the paper studies a link between the solvability of d-set agreement and (d, epsilon)-solo approximate agreement in asynchronous wait-free message-passing systems, which provides an insight on the "maximal partitioning" allowed to solve an approximate agreement task. (C) 2017 Elsevier B.V. All rights reserved.


Related material