Randomized Tree-Intersection Leader Election

Abstract

We present a randomized leader election algorithm for synchronous complete $n$-node graphs in the \textsf{CONGEST} model that introduces a highly tunable trade-off between time complexity and the per-node message complexity. By adjusting a single branching parameter, $\ell$, system designers can smoothly shift the algorithmic burden from execution time to per-node message complexity, all while maintaining a strictly sublinear total message complexity of $O(\sqrt{n}{\log }^{1.5}n)$. We achieve this by utilizing dynamically truncated $\ell$-ary tree expansions coupled with a novel ``silent pulse'' verification mechanism. By forcing the expansions to form exact-volume almost-complete trees, nodes can safely aggregate topological weights without overshooting the sublinear message bounds. Specifically, our algorithm achieves $O({\log }_{\ell }\sqrt{n\log n})$ time (round) complexity and $O(\ell )$ per-node message complexity. This flexibility allows networks with tight bandwidth constraints to operate with a minimal $O(1)$ per-node burden, while high-bandwidth environments can collapse the election into $O(1)$ time units.

Full version of a DISC 2026 paper