Constraints

𝒞 · 2026

Read Constraints by 𝒞 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-21022.txt.

Description

Standard definitions of the LOCAL model of distributed computing disagree on one point: do nodes update with arbitrary functions or only computable ones? Antonio Cruciani and six co-authors show the distinction matters in this 2026 arXiv paper, even for locally checkable labeling problems, the most studied family in this setting. Computability turns out to connect directly with knowledge of the graph size.

The authors exhibit a labeling problem solvable in logarithmically many rounds in the uncomputable model, and in the computable model when any upper bound on the size is known. Without any knowledge of size, the same problem needs a square-root number of rounds in the computable model. More generally, any size bound equalizes the two models for every labeling problem.

Catalog record

CREATOR𝒞
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-21022

Browse the full library · About the Tower of Babel