Search papers, labs, and topics across Lattice.
This paper provides a complete characterization of when randomized election algorithms exist in anonymous networks, considering both shared and unshared randomness. The analysis covers Las Vegas and Monte Carlo algorithms and generalizes previous deterministic results by considering arbitrary structural knowledge. The authors demonstrate how their general characterizations apply to specific knowledge scenarios like bounds on network size or the number of nodes sharing a random source, and relate existing randomized election algorithms to their framework.
Knowing bounds on network size or shared randomness sources is sufficient to solve the election problem in anonymous networks, offering a practical path to distributed decision-making.
We study the classical Election problem in anonymous net- works, where solutions can rely on the use of random bits, which may be either shared or unshared among nodes. We provide a complete char- acterization of the conditions under which a randomized Election algo- rithm exists, for arbitrary structural knowledge. Our analysis considers both Las Vegas and Monte Carlo randomized algorithms, under the as- sumptions of shared and unshared randomness. In our setting, random sources are considered shared if the output bits are identical across spe- cific subsets of nodes. The algorithms and impossibility proofs are extensions of those of [5] for the deterministic setting. Our results are a complete generalization of those from [8]. Moreover, as applications, we consider many specific knowledge: no knowledge, a bound on the size, a bound on the number of nodes sharing a source, the size, or the full topology of the network. For each of them, we show how the general characterizations apply, showing they actually correspond to classes of structural knowledge. We also de- scribe also how randomized Election algorithms from the literature fits in this landscape. We therefore provide a comprehensive picture illustrating how knowledge influences the computability of the Election problem in arbitrary anonymous graphs with shared randomness.
