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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01265958
Contributor : Michel Raynal <>
Submitted on : Monday, February 1, 2016 - 7:00:06 PM
Last modification on : Friday, January 11, 2019 - 2:24:36 PM
Long-term archiving on: Saturday, November 12, 2016 - 1:10:10 AM

Files

Synchrone-asynchrone-V31.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01265958, version 1

Citation

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⟩

Share

Metrics

Record views

1441

Files downloads

108