Leveraging Structural Knowledge for Solving Election in Anonymous Networks with Shared Randomness
摘要
We study the classical Election problem in anonymous networks, where solutions can rely on the use of random bits, which may be either shared or unshared among nodes. We provide a complete characterization of the conditions under which a randomized Election algorithm exists, for arbitrary structural knowledge. Our analysis considers both Las Vegas and Monte Carlo randomized algorithms, under the assumptions of shared and unshared randomness. In our setting, random sources are considered shared if the output bits are identical across specific subsets of nodes. The algorithms and impossibility proofs are extensions of those of Chalopin et al. (2012) for the deterministic setting. Our results are a complete generalization of those from Fraigniaud et al. (2024). 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 describe 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.