Distributed Computing in the Asynchronous LOCAL model

Understand

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 construction task $T$ associated to a locally checkable labeling (LCL), if $T$ is solvable in $t$ rounds in the LOCAL model, then $T$ remains solvable in $O(t)$ rounds in the asynchronous LOCAL model.