Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Wait-freedom and Locality are not Incompatible (with Distributed Ring Coloring as an Example)

Abstract : In the world of message-passing distributed computing, reliable synchronous systems and asyn-chronous failure-prone systems lie at the two ends of the reliability/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of wait-freedom is central to the second one. This paper is an attempt to reconcile these two extreme worlds, and benefit from both of them. To this end, it first proposes a new distributed computing model, where (differently from the two previous ones) processing and communication are decoupled. The communication component (made up of n nodes) is considered as reliable and synchronous, while the processing component (composed of n processes, each attached to a communication node) is asyn-chronous and any number of its processes may suffer crash failures. To illustrate the benefit of this model, the paper presents an asynchronous algorithm that, assuming a ring communication component , colors the processes with at most three colors. From a process crash failure point of view, this algorithm is wait-free. From a locality point of view, each process needs information only from processes at distance O(log * n) from it. This local wait-free algorithm is made up of a communication phase followed by a purely local simulation (by each process) of an extended version of Cole and Vishkin's vertex coloring algorithm (this extension does not require the processes to start simultaneously). This new communication/processing decoupled model seems to offer a promising approach for distributed computing.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Michel Raynal Connect in order to contact the contributor
Submitted on : Monday, February 1, 2016 - 7:00:06 PM
Last modification on : Friday, January 21, 2022 - 3:18:34 AM
Long-term archiving on: : Saturday, November 12, 2016 - 1:10:10 AM


Files produced by the author(s)


  • HAL Id : hal-01265958, version 1


Armando Castañeda, Carole Delporte, Hugues Fauconnier, Sergio Rajsbaum, Michel Raynal. Wait-freedom and Locality are not Incompatible (with Distributed Ring Coloring as an Example). 2016. ⟨hal-01265958⟩



Les métriques sont temporairement indisponibles