What can be computed in average anonymous networks?
Joel Rybicki, Oleg Verbitsky, Maksim Zhukovskii · 2026
Read What can be computed in average anonymous networks? by Joel Rybicki, Oleg Verbitsky, Maksim Zhukovskii (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-2604-02192.txt.
Introduction
Rybicki and colleagues ask what anonymous networks can compute when nodes lack IDs and merely broadcast to neighbors. In the weak SB and MB models, they give a one round deterministic algorithm that assigns unique IDs with high probability on random graphs. The method borrows from canonical labeling in graph isomorphism testing and can anonymize existing broadcast algorithms. They also find a triangle finding algorithm and show the weak model hierarchy collapses on these graphs, with SB nearly matching LOCAL.
Catalog record
| CREATOR | Joel Rybicki, Oleg Verbitsky, Maksim Zhukovskii |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105522 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.02192
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
What can be computed in average anonymous networks? Joel Rybicki, Oleg Verbitsky, Maksim Zhukovskii Abstract We study what deterministic distributed algorithms can compute on random input graphs in extremely weak models of distributed computing: all nodes are anonymous, and in each communication round, nodes broadcast a message to all their neighbors, receive a (multi)set of messages from their neighbors, and update their local state. These correspond to the 𝖲𝖡 \mathsf{SB} and 𝖬𝖡 \mathsf{MB} models introduced by Hella et al. [PODC 2012] and are strictly weaker than the standard port-numbering 𝖯𝖭 \mathsf{PN} and 𝖫𝖮𝖢𝖠𝖫 \mathsf{LOCAL} models. We investigate what can be computed almost surely on random input graphs. We give a one-round deterministic 𝖲𝖡 \mathsf{SB} -algorithm using O ( log n ) O(\log n) -bit messages that computes unique identifiers with high probability on anonymous networks sampled from G ( n , p ) G(n,p) , where n ε − 1 ≤ p ≤ 1 / 2 n^{\varepsilon-1}\leq p\leq 1/2 and ε > 0 \varepsilon>0 is an arbitrarily small constant. This algorithm is inspired by canonical labeling techniques in graph isomorphism testing and can be used to “anonymize” existing distributed graph algorithms designed for the broadcast 𝖢𝖮𝖭𝖦𝖤𝖲𝖳 \mathsf{CONGEST} and 𝖫𝖮𝖢𝖠𝖫 \mathsf{LOCAL} models. In particular, we give a new anonymous algorithm that finds a triangle in O ( 1 / ε ) O(1/\varepsilon) rounds on the above input distribution. We also investigate computational power of natural analogs of “Monte Carlo” and “Las Vegas” distributed graph algorithms in the random graph setting, and establish some new collapse and hierarchy results. For example, our work shows the collapse of the weak model hierarchy of Hella et al. on G ( n , p ) G(n,p) , as apart from a vanishingly small fraction of input graphs, the 𝖲𝖡 \mathsf{SB} model is as powerful as 𝖫𝖮𝖢𝖠𝖫 \mathsf{LOCAL} . 1 Introduction Many graph problems cannot be solved by deterministic, anonymous distributed algorithms for the simple reason that symmetry cannot be broken in worst-case graphs [ 3 , 61 , 62 ] . Thus, the typical approach is to assume nodes are given some symmetry breaking information as input, such as unique identifiers (e.g., the \mathsf{LOCAL} model [ 49 ] ), a stream of random bits (e.g., the port-numbering model \mathsf{PN} with private random bits), or locally unique identifiers (e.g., a suitable graph coloring [ 28 ] ). But if we move beyond worst-case inputs, to which extent is such additional symmetry breaking information necessary? Can anonymous, deterministic distributed algorithms perform well on most graphs? To address these questions, we study what can be computed by anonymous, deterministic algorithms on random input graphs sampled from the Erdős-Rényi random graph distribution G(n,p) . So far, even in the non-anonymous setting, the average-case complexity of distributed graph algorithms has remained largely unexplored apart from few isolated examples [ 48 , 46 , 19 , 58 ] . Our results in a nutshell. We investigate the question of what can be deterministically computed on “most” anonymous networks. We introduce and study the notions of asymptotically almost surely correct (“Monte Carlo”) and sound (“Las Vegas”) deterministic distributed algorithms on random input graphs. It turns out – somewhat surprisingly – that apart from a vanishingly small fraction of graphs, anonymous deterministic algorithms in very weak models of computing can solve any problem solvable in the \mathsf{LOCAL} model with only a small overhead in time and message length. This is because on most graphs identifiers can be deterministically generated in only one round using short O(\log n) -bit messages, allowing simulation of both \mathsf{LOCAL} and (broadcast) \mathsf{CONGEST} algorithms in weak anonymous models of computing. This further implies that a range of non-trivial tasks, such as finding Hamiltonian cycles or triangles, can be done fast on anonymous random graphs. 1.1 The setting: weak models of distributed computing We consider deterministic and anonymous distributed graph algorithms in the set-broadcast \mathsf{SB} and the multiset-broadcast \mathsf{MB} models. These models lie at the bottom of the weak model hierarchy introduced by Hella et al. [ 37 ] . In particular, both \mathsf{SB} and \mathsf{MB} models are strictly weaker than the standard port-numbering \mathsf{PN} and \mathsf{LOCAL} models of distributed computing. In the distributed setting, the input graph G=(V,E) on n nodes describes the communication topology of the distributed system, where nodes represent processors and edges communication links between processors. Each node v\in V is anonymous, but may additionally receive some local input f(v) , depending on the problem and the model of computing. In the set-broadcast model \mathsf{SB} , each node v\in V receives as local input its degree \deg(v) . All nodes run the same algorithm and computation proceeds in synchronous rounds, where in each round every node v\in V in parallel (1) broadcasts a single message to all its neighbors, (2) receives a set of messages broadcast by its neighbors, and (3) updates its local state. Once a node enters a stopping state, it halts with some output g(v) . In the \mathsf{SB} model, nodes cannot distinguish which neighbor sent which incoming message nor count the multiplicities of messages. In the multiset-broadcast model \mathsf{MB} , nodes receive multisets of messages instead of sets. That is, a node can also count the multiplicity of received messages. Otherwise, the two models are the same. 1 1 1 In particular, as in \mathsf{SB} , we assume that in \mathsf{MB} nodes know their degrees initially, although this could be learned in one communication round. The standard \mathsf{LOCAL} model is equivalent to the setting in which each node is given a unique identifier as local input. We also consider the “congested” variants of these models, where in each round nodes broadcast only short O(\log n) -bit messages. While the congested version of \mathsf{LOCAL} is known as the \mathsf{CONGEST} model, we denote the congested versions of \mathsf{SB} and \mathsf{MB} by \mathsf{SB}^{*} and \mathsf{MB}^{*} , respectively. Note that the \mathsf{SB}^{*} model with unique identifiers is (up to constant factors) equivalent to the broadcast \mathsf{CONGEST} model (abbreviated as \mathsf{B\mbox{-}CONGEST} ), where in each round each node broadcasts a single O(\log n) -bit message to all of its neighbors. 1.2 Distributed graph problems Graph problems. We consider problems on unlabeled graphs (i.e., the nodes or edges of the graph do not have input labels). Let \Gamma be a (possibly infinite) set of output labels. A graph problem \Pi associates to each graph G=(V,E) a set \Pi(G)\subseteq\Gamma^{V} of solutions. That is, a labeling \sigma\colon V\to\Gamma is a solution to \Pi on input G if \sigma\in\Pi(G) . We say that a problem \Pi is isomorphism-invariant if for any isomorphic pair of graphs G and H with an isomorphism \alpha from G to H we have that \Pi(G)=\{\sigma\circ\alpha:\sigma\in\Pi(H)\}. We say that \Pi is a component-wise problem if for every graph G and labeling \sigma\colon V\to\Gamma we have that \sigma\in\Pi(G) if and only if \sigma_{\restriction U}\in\Pi(H) for every connected component H=(U,F) of G , where \sigma_{\restriction U}\colon U\to\Gamma is the restriction of \sigma to the set U\subseteq V . Throughout, we consider only isomorphism-invariant, component-wise graph problems. This definition covers many typical problems, in particular, all problems on unlabeled graphs that are solvable in the uniform \mathsf{LOCAL} model (where nodes do not a priori know