Making local algorithms wait-free: the case of ring coloring
type: Item
instance of: scholarly article
title: Making local algorithms wait-free: the case of ring coloring
zbMATH Open document ID: 1423.68068
author: Armando Castañeda
author: Carole Delporte-Gallet
author: Hugues Fauconnier
author: Sergio Rajsbaum
author: Michel Raynal
published in: Theory of Computing Systems
publication date: 2019-06-21T00:00:00Z
Mathematics Subject Classification ID: 68M14
Mathematics Subject Classification ID: 68M15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 7070406
zbMATH Keywords: synchronous distributed computing
zbMATH Keywords: Cole and Vishkin's coloring algorithm
zbMATH Keywords: locality of a computation
zbMATH Keywords: message-passing
zbMATH Keywords: process crash failure
zbMATH Keywords: synchronous communication
zbMATH Keywords: vertex coloring problem
zbMATH Keywords: wait-freedom
MaRDI profile type: MaRDI publication profile
full work available at URL: s00224-017-9772-y
OpenAlex ID: W2611796538
cites work: Efficiency of Synchronous Versus Asynchronous Distributed Systems
cites work: Complexity of network synchronization
cites work: Deterministic \((\Delta+1)\)-coloring in sublinear (in \(\Delta\)) time in static, dynamic, and faulty networks
cites work: Deterministic distributed vertex coloring in polylogarithmic time
cites work: Distributed Graph Coloring: Fundamentals and Recent Developments
cites work: Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
cites work: Deterministic coin tossing with applications to optimal parallel list ranking
cites work: Impossibility of distributed consensus with one faulty process
cites work: Towards a complexity theory for local distributed computing
cites work: Q4198056
cites work: Parallel Symmetry-Breaking in Sparse Graphs
cites work: What cannot be computed locally!
cites work: Locality in Distributed Graph Algorithms
cites work: What Can be Computed Locally?
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: Concurrent programming: algorithms, principles, and foundations.
cites work: Survey of local algorithms
DOI: 10.1007/S00224-017-9772-Y
Recommended article: Making local algorithms wait-free: the case of ring coloring
Recommended article: Locality in Distributed Graph Algorithms
Recommended article: Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
Recommended article: What Can be Computed Locally?
Recommended article: On the locality of some NP-complete problems
description: scientific article; zbMATH DE number 7070406