• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 24 Feb 2026] Title:Is a LOCAL algorithm computable? • View PDF HTML (experimental)Abstract:Common definitions of the “standard” LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a computable function? • So far, this distinction has been safe to neglect, since problems where it matters seem contrived and quite different from e.g. • typical local graph problems studied in this context. • We show that this question matters even for locally checkable labeling problems (LCLs), perhaps the most widely studied family of problems in the context of the LOCAL model. • Furthermore, we show that assumptions about computability are directly connected to another aspect already recognized as highly relevant: whether we have any knowledge of $n$, the size of the graph.

Article Summaries:

  • Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 24 Feb 2026] Title:Is a LOCAL algorithm computable? View PDF HTML (experimental)Abstract:Common definitions of the “standard” LOCAL model tend to be sloppy and even self-contradictory on one point: do the nodes update their state using an arbitrary function or a computable function? So far, this distinction has been safe to neglect, since problems where it matters seem contrived and quite different from e.g. typical local graph problems studied in this context. We show that this question matters even for locally chec

Sources: