Distributed computing in the asynchronous LOCAL model

The LOCAL model is among the main models for studying locality in the framework of distributed network computing. This model is however subject to pertinent criticisms, including the facts that all nodes wake up simultaneously, perform in lock steps, and are failure-free. We show that relaxing these...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2025-02, Vol.1025, p.114952, Article 114952
Main Authors: Delporte-Gallet, Carole, Fauconnier, Hugues, Fraigniaud, Pierre, Rabie, Mikaël
Format: Article
Language:English
Subjects:
Asynchrony
Distributed network computing
Fault-tolerance
Locality
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The LOCAL model is among the main models for studying locality in the framework of distributed network computing. This model is however subject to pertinent criticisms, including the facts that all nodes wake up simultaneously, perform in lock steps, and are failure-free. We show that relaxing these hypotheses to some extent does not hurt local computing. In particular, we show that, for any task T associated to a locally checkable labeling (lcl), if T is solvable in t rounds by a deterministic algorithm in the LOCAL model, then T remains solvable by a deterministic algorithm in O(t) rounds in an asynchronous variant of the LOCAL model whenever t=O(polylogn). This improves the result by Castañeda et al. [TCS, 2019], which was restricted to 3-coloring the rings. More generally, the main contribution of this paper is to show that, perhaps surprisingly, asynchrony and failures in the computations do not restrict the power of the LOCAL model, as long as the communications remain synchronous and failure-free. To this end, this paper introduces a new distributed renaming technique to provide nodes with consistent identifiers.
ISSN:0304-3975
DOI:10.1016/j.tcs.2024.114952