One of the most successful theoretical models in distributed computing is the LOCAL one, introduced in a seminal work by Linial [SIAM J. Comp. 1992]. Over the years, when studying distributed graph problems in the LOCAL model, researchers made different assumptions on the exact details of this model. For example, sometimes it is assumed that all machines know the exact size of the network, other times machines are assumed to only know a polynomial upper bound on the size of the network, while sometimes no prior knowledge is assumed. Are these small differences irrelevant details or do they actually heavily affect the obtained results? We investigate how robust our current understanding of the LOCAL model truly is, by focusing on one of the most studied classes of problems, called Locally Checkable Labelings (LCLs). LCLs are graph problems for which correct solutions can be described by listing a finite set of valid constant-radius neighborhoods. Since Naor and Stockmeyer introduced LCLs [FOCS 1995], understanding them has been in the center of attention, and, in the last 10 years, researchers were able to make a lot of progress. For example, Chang, Kopelowitz, and Pettie [FOCS 2016] showed that the randomized complexity of any LCL problem on n-node graphs is at least its deterministic complexity on sqrt(log n)-node graphs, where n is the total number of nodes in the graph. Later, Chang and Pettie [FOCS 2017], among other things, showed that, on bounded-degree trees, any randomized algorithm solving an LCL in n^{o(1)} rounds can be automatically transformed into a deterministic algorithm with runtime O(log n). Then, Balliu, Hirvonen, Korhonen, Lempiäinen, Olivetti, and Suomela [STOC 2018] showed that these kind of automatic speedups are no longer possible for general bounded-degree graphs. The above-mentioned results make use of the assumption that the nodes have, for free, prior knowledge of n. How much does this assumption affect the beautiful theory of LCLs as we know it nowadays? It turns out that, perhaps surprisingly, if we were to consider a setting where nodes are oblivious of n, or if we relax the setting such that nodes know a polynomial upper bound of n, already on trees, the theory of LCLs looks quite different from the one we currently know. In fact, while the fundamental classification of problems seems to remain the same, our results show that the picture becomes much more complex: for example, there are more cases in which randomness helps in solving LCLs faster; there are problems with very unnatural complexities; and for some problems the exact lower bound even depends on which definition of Ω we use!
ACM Symposium on Principles of Distributed Computing (PODC)
2026-07-06
2026-05-04