Search papers, labs, and topics across Lattice.
This paper investigates the computational power of deterministic distributed algorithms on random input graphs in extremely weak anonymous network models (SB and MB). They present a one-round deterministic SB-algorithm using $O(\log n)$-bit messages that computes unique identifiers with high probability on $G(n,p)$ graphs where $n^{\varepsilon-1} \le p \le 1/2$. This algorithm, inspired by graph isomorphism testing, effectively "anonymizes" existing distributed algorithms and leads to a new anonymous triangle-finding algorithm.
Forget port numbering: surprisingly, anonymous networks with simple broadcast can compute unique identifiers and even find triangles in random graphs almost as powerfully as standard distributed models.
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 SB and MB models introduced by Hella et al. [PODC 2012] and are strictly weaker than the standard port-numbering PN and LOCAL models. We investigate what can be computed almost surely on random input graphs. We give a one-round deterministic SB-algorithm using $O(\log n)$-bit messages that computes unique identifiers with high probability on anonymous networks sampled from $G(n,p)$, where $n^{\varepsilon-1} \le p \le 1/2$ and $\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 CONGEST and LOCAL models. In particular, we give a new anonymous algorithm that finds a triangle in $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)$, as apart from a vanishingly small fraction of input graphs, the SB model is as powerful as LOCAL.
