2017/12/12 by Delporte-Gallet, Carole, Fauconnier, Hugues, Rajsbaum, Sergio +1
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1712.04393
A task is a distributed problem for n processes, in which each process starts with a private input value, communicates with other processes, and eventually decides an output value. A task is colorless if each process can adopt the input or output value of another process. Colorless tasks are well studied in the non-anonymous shared-memory model where each process has a distinct identifier that can be used to access a single-writer/multi-reader shared register. In the anonymous case, where processes have no identifiers and communicate through multi-writer/multi-reader registers, there is a recent topological characterization of the colorless tasks that are solvable when any number of asynchronous processes may crash. In this paper we study the case where at most t processes may crash, where 1 ≤ t < n. We prove that a colorless task is t-resilient solvable non-anonymously if and only if it is t-resilient solvable anonymously. This implies a complete characterization of colorless anonymous t-resilient asynchronous task computability.