Randomized Tree-Intersection Leader Election

Randomized Tree-Intersection Leader Election Yuval Emek # Technion, Israel

Shay Kutten # Technion, Israel

Ido Rafael # Technion, Israel

Gadi Taubenfeld # Reichman University, Israel

arXiv:2608.08817v1 [cs.DC] 9 Aug 2026

Abstract We present a randomized leader election algorithm for synchronous complete n-node graphs in the CONGEST model that introduces a highly tunable trade-off between time complexity and the per-node message complexity. By adjusting a single branching parameter, ℓ, 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( n log1.5 n). We achieve this by utilizing dynamically truncated ℓ-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ℓ n log n) time (round) complexity and O(ℓ) 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. 2012 ACM Subject Classification Theory of computation → Distributed computing models; Theory of computation → Distributed algorithms Keywords and phrases Leader election, randomized algorithms, sublinear communication, per-node message complexity, CONGEST model. Funding Yuval Emek: Partially supported by an Israel Science Foundation (ISF) grant 730/24 and by The Bernard M. Gordon Center for Systems Engineering at the Technion. Shay Kutten: Partially supported by Israel Science Foundation (ISF) grant 1346/22 and by The Bernard M. Gordon Center for Systems Engineering at the Technion and by the Technion’s Grand Energy program.

1

Introduction

Leader election is a fundamental symmetry-breaking problem in distributed computing, serving as a vital primitive for tasks ranging from token passing to consensus and spanning tree construction. In modern, large-scale networks, algorithms must not only be efficient in terms of time and total communication, but they must also reduce and balance the total communication burden placed on individual nodes. We focus on the implicit leader election problem, where the fundamental requirement is that exactly one node terminates in a leader state, while all others terminate in a non-leader state. This is in contrast to explicit leader election, which imposes the heavier requirement that every node in the network must also learn the unique identifier of the elected leader. While significant progress has been made in optimizing the total message complexity and execution time of implicit leader election [4, 5, 6, 7, 8, 9], less effort has been made toward improving the total communication burden placed on individual nodes. While total message complexity captures the aggregate communication cost of an algorithm, it often masks severe imbalances in how this burden is distributed across the network.

2

Randomized Tree-Intersection Leader Election

In many modern distributed systems – such as wireless sensor networks, IoT deployments, and ad-hoc mobile networks – individual nodes operate under strict energy and local bandwidth constraints. An algorithm with an optimal total message complexity might still overwhelm a small subset of nodes, rapidly depleting their batteries or creating severe local congestion hotspots that degrade overall network throughput. Consequently, bounding the per-node message complexity is an important requirement for ensuring equitable resource consumption, avoiding single points of failure, and extending the operational lifetime of the network. Beyond constraining the processing and energy burden on individual nodes, bounding the total per-node message complexity inherently restricts overall link congestion throughout the algorithm’s execution. While the standard CONGEST model limits the bandwidth on any edge per round, an algorithm with a total per-node message complexity of O(X) strictly guarantees a total per-edge message complexity of O(X) across all rounds. Since the converse does not hold—a network may maintain low per-edge traffic while still overwhelming high-degree nodes—optimizing for per-node complexity serves as a strictly stronger condition that prevents both node-level and link-level bottlenecks over the entire execution. In this paper, we present a randomized leader election algorithm for synchronous complete n-node graphs that introduces a highly tunable trade-off between time complexity and pernode message complexity. We achieve this through a novel “tree-intersection” strategy. Rather than relying on fixed-topology message passing, our algorithm allows candidates to initiate an ℓ-ary tree expansion, and ensure that the trees initiated by different candidates intersect with high probability. However, a major technical hurdle arises when ℓ is large: a naive, perfect tree expansion could overshoot the required footprint by a factor of ℓ, ruining the algorithm’s sublinear communication guarantees.1 We overcome this by forcing the expansion to build an almostcomplete tree.2 By embedding an explicit leaf-allocation budget within messages, nodes dynamically truncate the expansion the precise round the exact target footprint is satisfied. To achieve time and message efficiently (and simplicity) within the strict O(log n)-bit bandwidth limit of the CONGEST model, we introduce two novel algorithmic mechanisms: the “silent pulse” optimization and a “conservation of weight” principle. Instead of explicitly tracking duplicate branches or pruned paths, our framework relies on strict layer-by-layer synchronization. A parent node expects an acknowledgment from its children at a precisely calculated round. If a branch is pruned by a higher-rank candidate or absorbed due to an internal collision, it silently drops out of the communication flow. By treating nonarriving messages as zero weight, the algorithm securely aggregates acknowledgments without requiring explicit rejection messages, maintaining the structural integrity of the tree. We note a fundamental topological barrier: it is impossible to design an algorithm that achieves this highly tunable trade-off between time and per-node message complexity for arbitrary network topologies. This limitation is best illustrated by a double star graph.3 In a double star topology, any symmetry-breaking process that requires a total message complexity of M inherently forces the two center nodes to act as a routing bottleneck. Consequently, the two center nodes must process a fraction of the messages proportional to Ω(M ). Because the local load is dictated by the graph’s structure rather than the algorithm’s design, the per-node message complexity cannot be decoupled from the total message complexity, preventing the

1

The stopping condition for a perfect tree is very simple because all leaves reside on the last level. An almost complete tree is a tree structure where every level is completely filled, except possibly the last level. Thus, all leaves reside on the last two levels. 3 A graph composed of two star graphs whose central vertices are connected by an edge is called a double star graph. We notice that in a star graph the single center node can simply elect itself. 2

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

3

existence of a universal, topology-independent algorithm with a tunable trade-off between time and per-node message complexity. √ The branching factor, 1 ≤ ℓ ≤ 2 n log n, serves as the algorithmic dial. As summarized in Table 1, scaling ℓ allows to smoothly shift the computational burden from time to per-node √ complexity, all while maintaining a sublinear total message complexity of O( n log1.5 n). √ Table 1 The Complexity Frontier: Trade-offs based on Branching Factor 1 ≤ ℓ ≤ 2 n log n Branching Factor (ℓ) ℓ = 1 (Walk) ℓ = 2 (Binary Tree) √ ℓ = 2 n log n (Star) General ℓ (ℓ ≥ 2)

Time Complexity √ O( n log n) √ O(log n log n) O(1) √ O(logℓ n log n)

Per-Node Messages O(1) O(1) √ O( n log n) O(ℓ)

Total Messages √ O( n log1.5 n) √ O( n log1.5 n) √ O( n log1.5 n) √ O( n log1.5 n)

While branching factors of ℓ ≥ 2 offer exponential speedups in latency, the baseline case of ℓ = 1 remains crucial for strictly constrained networks. Although both ℓ = 1 and ℓ = 2 share the same O(1) per-node message complexity, the ℓ = 1 configuration yields smaller constant factors. By relying on a single propagating path rather than coordinating multiple concurrent branches, it strictly minimizes local memory state and bandwidth overhead. This minimalist extreme is the starting point of the tunable spectrum our framework provides. The parameterized approach we use frames our work not merely as a new algorithm, but as a generalization of the state-of-the-art for complete graphs. Prior innovative work by Kutten et al. [9] established strict sublinear bounds for randomized leader election. Their algorithm achieves an impressive O(1) time complexity, but inherently requires an √ O( n log n) per-node message complexity. Viewed through the lens of our framework, the algorithm in [9] for complete graphs operates at the extreme edge of our complexity frontier, √ analogous to setting the branching factor to ℓ = 2 n log n. Conversely, our baseline path-intersection algorithm (ℓ = 1, first line of Table 1) represents the opposite extreme. By introducing the ℓ-ary tree expansion, we unlock the entire continuous spectrum between these two extremes. This flexibility allows networks with tight bandwidth or energy constraints (such as ad-hoc or sensor networks) to operate with a minimal O(1) per-node burden, while high-bandwidth environments with less energy constraints (such as data centers) can collapse the election into constant time. The remainder of this paper is organized as follows. Section 2 formally defines the computational model. In Section 3 we present the path-intersection algorithm which is a simplified special version of the tree-intersection algorithm. In Section 4, we introduce the tree-intersection algorithm. Section 5 situates our contribution within the broader literature, and finally, Section 6 concludes the paper and discusses open questions for future work.

2

Model and Preliminaries

Communication Model. We model the communication network as an undirected, connected complete graph G = (V, E), where V is the set of nodes with |V | = n and E is the set of communication links. We assume the system is fully synchronous, meaning execution proceeds in discrete, globally synchronized rounds. To avoid ambiguity, we explicitly define the anatomy of a synchronous round in our model. Each round consists of two consecutive steps: first, a send step where each node evaluates its

4

Randomized Tree-Intersection Leader Election

local state and transmits messages to its neighbors; second, a receive step where the messages sent in the current round arrive and are processed by the node to update its state. Communication strictly adheres to the CONGEST model: in the send step of each round, any node can send a potentially distinct message to each of its neighbors in G, provided the size of each message is strictly bounded by O(log n) bits. Each node v ∈ V is anonymous. During the algorithm execution, each node draws, from a polynomial space, a unique identifier IDv (unique w.h.p.). All nodes have knowledge of n. Complexity Measures. We evaluate the efficiency of our algorithms using the following three standard metrics: Time Complexity: The total number of synchronous communication rounds required from the initiation of the algorithm until the final node safely terminates and the system reaches its final state. Total Message Complexity: The aggregate number of O(log n)-bit messages transmitted across all communication links in the network over the entire execution of the algorithm. Per-Node Message Complexity: The maximum number of O(log n)-bit messages processed (sent or received) by any single individual node throughout the algorithm’s execution. Implicit Leader Election. Initially, all nodes are in a uniform initial state. The goal of the algorithm is to break symmetry and elect a single leader. An algorithm successfully solves implicit leader election if, upon termination of the algorithm, the following conditions hold: (1) Exactly one node terminates in the leader state, and (2) All other nodes terminate in a non-leader state. Crucially, there is no requirement for nodes terminating in the non-leader state to know the ID of the elected leader [10]. This termination condition avoids the trivial Ω(n) message complexity lower bound known for explicit leader election. The notion “with high probability”. For simplicity, since we generalize results from [9], we will use the same definition used in [9]. An event occurs with high probability if, for some constant c ≥ 1, the probability of the event occurring is at least: 1 − n−c . Our results can easily be adapted (by scaling up the constant coefficients in our sample sizes and branch volumes accordingly) to satisfy the following stronger definition [2, 11]: An event A occurs with high probability if Pr(A) ≥ 1 − n−c for any (arbitrarily large) constant c ≥ 1.

3

Randomized Path-Intersection Leader Election

The path-intersection algorithm, presented in this section, is a simplified, special version of the more complex tree-intersection algorithm presented in the next section. We present the path-intersection approach separately for two key reasons. First, it serves as a pedagogical stepping stone, demonstrating the core random-walk intersection and trace-back mechanics without the added complexities of internal collisions and weight aggregation. Second, in strictly constrained networks where ℓ = 1 is the optimal operating point, Algorithm 1 provides better constant factors in terms of local memory and processing overhead. In Algorithm 1, initially, each node independently becomes a candidate with probability p = logn n . This probability ensures that at least one and at most 4 log n nodes become candidates w.h.p. Then, each candidate v chooses a random rank rv ∈ {1, . . . , n4 }, which ensures that the ranks are unique w.h.p. due to the domain size n4 . Candidates are whittled down through intersecting random walks. Each candidate creates a token with a unique rank which starts a random walk. To stay within the CONGEST

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

bandwidth limits, every node only agrees to pass along the single highest-ranked token it has seen so far, effectively disqualifying smaller competitors on the spot. Only the token that manages to be the maximum at every single step of its random walk will reach the end of the walk and find a path (of stored edges) to follow back to the candidate that generated it. If a candidate sees its own token returns, it knows it is the global winner. √ The full length of the random walks is L = 2 × ⌈ n log n⌉ − 1, and it ensures that the walks are long enough to encounter one another w.h.p. To ensure the global winner is correctly identified even if ranks intersect at different times, a returning token is only permitted to continue its journey if its rank remains the highest ever seen by every node on its path, discarding any earlier tokens that were surpassed by a late-arriving superior rank. The advantage of the path-intersection algorithm is its very low per-node message complexity, only O(1) messages, which improves upon the previously best known per-node √ message complexity of 2 × ⌈ n log n⌉ [9]. Its core limitation is its sequential nature which √ leads to high time complexity, 2 × ⌈ n log n⌉ rounds, compared to one round of the algorithm √ of [9]. Both algorithms ([9] and ours) have the same O( n log1.5 n) total message complexity.

3.1

The algorithm

Algorithm 1 Path-Intersection Leader Election in Complete Graphs The following code is executed by each node v ∈ V Constants (known to all nodes): G = (V, E) ▷ G is a complete graph √ where |V | = n L = 2 × ⌈ n log n⌉ − 1 ▷ length of a random walk State Variables at node v: 1: rmax ← 0; rv ← 0; flag ← false; status ← ⊥; prev_hop[1 . . . L] ← ⊥ ▷ initialization Phase 1: Candidate Selection (Round 0) 2: Node v independently becomes a candidate with probability p = logn n 3: if v is a candidate then 4: rv ← generate a random rank from {1, . . . , n4 } ▷ unique rank w.h.p. 5: Tv ← create token ⟨rv ⟩; rmax ← rv ; flag ← true ▷ ready to forward Tv 6: Tbest ← Tv ▷ Tbest and Tv refer to the same token Phase 2: Forward Random Walk (Rounds 1 to L) 7: for round i = 1 to L do ▷ global rounds 1 to L 8: if flag = true then ▷ one step of the random walk 9: Select edge to neighbor u ∈ N (v) u.a.r. and forward Tbest to u; flag ← false 10: if v receives one or more tokens in the current round then ▷ updates Tbest 11: Tbest ← the token with maximum rank among the received tokens 12: if rbest ≥ rmax then ▷ rbest denotes the rank of Tbest 13: rmax ← rbest ; flag ← true ▷ ready to forward Tbest 14: prev_hop[i] ← arrival edge from sender of Tbest ▷ facilitate trace-back 15: else drop Tbest ▷ disqualified by a higher rank that arrived earlier Phase 3: Trace-back and Verification (Rounds L + 1 to 2L) 16: for round i = 1 to L do ▷ global rounds L + 1 to 2L 17: if flag = true then 18: Forward Tbest via edge prev_hop[L − i + 1]; flag ← false ▷ a retrace step 19: if v receives token Tu in the current round then ▷ v can receive at most one token! 20: if ru = rmax then ▷ it is not possible that ru > rmax 21: Tbest ← Tu ; flag ← true ▷ ready to forward Tbest 22: else drop Tbest ▷ disqualified by a higher rank that arrived later Phase 4: Termination (Round 2L + 1) 23: if v is a candidate and v receives its own token Tv in Round 2L and rv = rmax then 24: status ← LEADER else status ← NOT_LEADER

5

6

Randomized Tree-Intersection Leader Election

3.2

Correctness and Complexity Analysis of Algorithm 1

At the heart of our approach is the well-known combinatorial phenomenon often referred to as the Birthday Paradox [11]. This phenomenon inspired the following lemma which captures the high probability of intersection between any two random walks of sufficient length. ▶ Lemma 1 (Random Walk Intersection Probability). In a complete graph Kn , let √W1 and W2 be two independent random walks generated by Algorithm 1, each of length L = 2 n log n −1. The probability that W1 ∩ W2 = ∅ is at most n−4 .  √ Proof. Let X1 , . . . , XN and Y1 , . . . , YN be the N = L + 1 = 2 n log n nodes visited by W1 and W2 , respectively, in the order in which they are visited, where X1 and Y1 are the starting nodes of the walks. Define SX := {X1 , . . . , XN } and D := |SX |. The event W1 ∩ W2 = ∅ is equivalent to ∀j ∈ [N ] : Yj ∈ / SX . Hence, by the chain rule, for every realization SX = S, Pr[W1 ∩ W2 = ∅ | SX = S] =

N Y

Pr[Yj ∈ / S | Y1 , . . . , Yj−1 ∈ / S, SX = S] .

j=1

Let us bound each term in the product. For j = 1, we use the trivial upper bound 1. For every j ≥ 2, under the above conditioning the current step Yj−1 of W2 lies outside S. Let d = |S|. Since S contains d distinct nodes, the events of moving to each of these nodes in the next step Yj are disjoint. Thus, the probability that the walk enters S in the next step is exactly d/(n − 1). Therefore, 

d Pr[W1 ∩ W2 = ∅ | SX = S] ≤ 1 · 1 − n−1

N −1

  d(N − 1) ≤ exp − . n−1

Averaging the preceding bound over all realizations SX = S with |S| = d, we get   d(N − 1) . Pr[W1 ∩ W2 = ∅ | D = d] ≤ exp − n−1 It remains to lower-bound D. For t ∈ [N ], let It = 1[Xt ∈ / {X1 , . . . , Xt−1 }]. Then D = PN I . Reveal X , . . . , X sequentially. For t = 1, we have I1 = 1. For t ≥ 2, if by step 1 N t=1 t t − 1 the walk has visited k distinct nodes, then Xt−1 is one of these k nodes, and among the n − 1 possible choices for Xt , at most k − 1 are old. Since k ≤ t − 1 ≤ N = o(n), for all sufficiently large n, Pr[It = 1 | X1 , . . . , Xt−1 ] ≥ 1 −

k−1 7 ≥ . n−1 8

Hence D stochastically dominates Bin(N, 7/8).4 By a Chernoff bound,   (1/7)2 · (7N/8) Pr[D < 3N/4] ≤ Pr[Bin(N, 7/8) < 3N/4] ≤ exp − ≤ e−Ω(N ) . 2 Using the bound conditioned on D = d and splitting according to whether D < 3N/4,   3N (N − 1) Pr[W1 ∩ W2 = ∅] ≤ e−Ω(N ) + exp − . 4(n − 1)

4

This is the standard coupling: if qt = Pr[It = 1 | X1 , . . . , Xt−1 ], then qt ≥ 7/8. Using independent Ut ∼ Unif[0, 1], one may realize It = 1[Ut ≤ qt ], while Bt = 1[Ut ≤ 7/8] are independent Bernoulli (7/8) variables and satisfy Bt ≤ It for all t.

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

Since N = 2

√

7

 n log n ,

  3N (N − 1) 3 ≥ (3 − o(1)) log n = − o(1) ln n. 4(n − 1) ln 2   (N −1) ≤ n−4.1 = o(n−4 ). As 3/ ln 2 > 4.3, we have exp − 3N 4(n−1) Also, e−Ω(N ) = o(n−4 ). Thus both terms above are o(n−4 ), and in particular, for all sufficiently large n, their sum is at most n−4 . Therefore, Pr[W1 ∩ W2 = ∅] ≤ n−4 . ◀ ▶ Lemma 2 (Unambiguous Path Retraction). For any token T that completes Phase 2 at round L, the sequence of edges traversed in Phase 3 is the exact reverse of the sequence of edges traversed in Phase 2, regardless of possible cycles. Proof. Let the forward path of T be represented as a sequence of nodes P = (v0 , v1 , . . . , vL ). In each round i ∈ {1, . . . , L}, node vi receives the token from vi−1 and stores the arrival edge in prev_hop[i]. If the path contains a loop such that va = vb for a ̸= b, the node va will store two distinct arrival edges in two distinct memory locations: prev_hop[a] and prev_hop[b]. In Phase 3, during round j ∈ {1, . . . , L}, the node currently holding the token uses the index k = L − j + 1 to select its next hop. Since j increments linearly, k decrements linearly from L to 1. This ensures that at any round j, the node vL−j+1 retrieves exactly the edge prev_hop[L − j + 1] that points back to vL−j , effectively reconstructing the path P ′ = (vL , vL−1 , . . . , v0 ). Because the indexing is tied to the global synchronous round, the physical identity of the nodes does not cause ambiguity. ◀ ▶ Theorem 3 (Safety). With high probability, the algorithm elects at most one leader. Proof. Let C be the set of candidates. If |C| = 0, no leader is elected. If |C| ≥ 1, let vmax be the candidate with the unique maximum rank rankmax (ranks are unique w.h.p. due to the domain size n4 ).5 Suppose for contradiction a candidate u = ̸ vmax with rank ru < rankmax is elected. For u to be elected, its token Tu must successfully complete the Trace-back Phase. This implies that for every node on u’s path, the condition ru = rmax held true during the retrace steps. However, by Lemma 1, the random walk of u and the random walk of vmax intersect at some node z with high probability. Furthermore, the phases ensure that all “forward” messages happen before all “rebound” messages. When vmax ’s token Tmax visited z (during Phase 2), node z updated rmax ← rankmax . By Lemma 2, Tu must retrace through z. Since rankmax > ru , any subsequent attempt by Tu to retrace through z would fail the check ru = rmax at node z, causing Tu to be dropped. Thus, u cannot be elected. ◀ ▶ Theorem 4 (Liveness). With high probability, exactly one leader is elected. Proof. No candidate is selected with probability ≈ (1 − p)n , negligible for p = logn n . The candidate vmax with the global maximum rank rankmax will never have its token dropped. In Phase 2, for any node w visited by Tmax , the local variable rmax of w is updated to rankmax because no rank is strictly greater than rankmax . In Phase 3, the condition rankmax = rmax will hold at every step of the trace-back. Thus, Tmax returns to vmax , and vmax is elected. Combined with Theorem 3, exactly one leader is elected. ◀ ▶ Theorem 5 (CONGEST). The constraint of the CONGEST model is satisfied. 5

The probability that any two of the n nodes select the same rank is bounded by even if every node selects a rank, all ranks are unique with high probability.

n 1 1 2 n4 < 2n2 . Thus,

8

Randomized Tree-Intersection Leader Election

Proof. If a token Tu is not the maximum at some point in its forward random walk, it is dropped. Thus, in such a case, Tu never starts the Trace-back Phase and never returns to the candidate. By filtering for Tbest in Phase 2, we reduce the message complexity to at most one message per node per round. In Phase 3, a token T will return to a node v at a given round, say i, only if it was submitted by v 2(L − i) rounds earlier, which implies that a node will not receive more than one token in any round during Phase 3. Thus, a node can only send one O(log n)-bit message per round per edge. ◀ ▶ Theorem 6 (Complexity Bounds). Algorithm 1 achieves the following bounds w.h.p.: √  √ 1. Time Complexity: 4 × n log n − 2 = O( n log n) rounds. √ 2. Total Message Complexity: O( n log1.5 n) messages. 3. Per-Node Message Complexity: O(1) messages. Proof. Time: The algorithm runs for exactly 2L rounds. Round 0 and 2L + 1 are not √ counted as they do not involve communication. With L = 2×⌈ n log n⌉−1, time is as claimed. Total Messages: Let C be the set of candidates. Since each node becomes a candidate with probability p = logn n , the expected number of candidates is E[|C|] = n · logn n = log n. By Chernoff bounds, |C| ≤ 4 log n w.h.p.6 Each candidate generates exactly one token that travels at most L steps forward and L steps back. The total number of messages is at most |C|·2L. √ √ √ Substituting L = 2 × ⌈ n log n⌉ − 1, w.h.p.: M ≤ (4 log n) · 4⌈ n log n⌉ = O( n log1.5 n). Per-Node Complexity: Fix a node v. We bound the number of forward messages received by v. Let XvF denote this number. Let E be the event that |C| ≤ 4 log n. As shown above, Pr[¬E] ≤ n−3.67 . Condition on an arbitrary candidate set C such that |C| ≤ 4 log n. Order all possible forward trials in some fixed order, for example first by the ID of the candidate that √ generated the token, and then by the step number of the token. Let N = L + 1 = 2⌈ n log n⌉. There are at most 4N log n such trials. For the ith trial, let Ii be the indicator for the event P4N log n that the corresponding forward message is received by v. Then XvF = i=1 Ii . The indicators Ii are not necessarily independent. However, for every history of the process before the ith trial, the probability that the next forward message is received by v is at most 1/(n − 1). Indeed, if the token is currently at v, then the probability that the next message is received by v is 0; otherwise, the next node is chosen uniformly among the n − 1 neighbors. Thus, conditioned on E, random variable XvF is stochastically dominated by the random variable Y ∼ Bin(4N log n, 1/(n − 1)).7 Therefore, for every fixed integer k, Pr[XvF ≥ k | E] ≤ Pr[Y ≥ k]. If Y ≥ k, then there exists a set S of k successful trials. Therefore, by a union bound over all such sets S,   k  k X 4N log n 1 1 4N log n Pr[Y ≥ k] ≤ Pr[all trials in S are successful] = ≤ . k n−1 k! n−1 S⊆[4N log n] |S|=k

We use a common form of the Chernoff bound P (X ≥ (1 + δ)µ) ≤ (eδ /(1 + δ)(1+δ) )µ , where: µ = log n, and δ = 3. Thus, P (|C| ≥ 4 log n) ≤ (e3 /44 )log n ≤ (0.078)log n = nlog(0.078) ≈ n−3.68 7 This is the standard coupling under the conditioning on E: if qi = Pr[Ii = 1 | E, Hi−1 ], where Hi−1 is the full history before the ith trial, then qi ≤ 1/(n − 1). Using independent Ui ∼ Unif[0, 1], one may realize Ii = 1[Ui ≤ qi ], while Bi = 1[Ui ≤ 1/(n − 1)] are independent Bernoulli (1/(n − 1)) variables and satisfy Ii ≤ Bi for all i. 6

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

9

√ Taking k = 6 and using N = 2⌈ n log n⌉, we get  9  log n F Pr[Xv ≥ 6 | E] = O . n3 By a union bound over all nodes, Pr[∃v ∈ V : XvF ≥ 6 | E] ≤ n · O



log9 n n3



 =O

log9 n n2

 .

Thus, Pr[∃v ∈ V : XvF ≥ 6] ≤ Pr[¬E] + Pr[∃v ∈ V : XvF ≥ 6 | E] ≤ n−3.67 + O



log9 n n2

 ≤

1 , n

for all sufficiently large n. Thus, with probability at least 1 − 1/n, every node receives at most 5 forward messages. It remains to translate this into total processed messages, namely sent and received messages in both the forward and trace-back phases. During the forward phase, every non-initial forward message sent by v is caused by a previous forward message received by v. In addition, v may send one initial message if it is a candidate. Hence, the number of forward messages sent by v is at most XvF + 1. During the trace-back phase, every trace-back message sent by v corresponds to a forward message previously received by v, and every trace-back message received by v corresponds to a forward message previously sent by v. Therefore, the number of trace-back messages sent by v is at most XvF , and the number of trace-back messages received by v is at most XvF + 1. Consequently, the total number of messages processed by v is at most XvF + (XvF + 1) + XvF + (XvF + 1) = 4XvF + 2. Therefore, with probability at least 1 − 1/n, every node processes at most 22 messages. Thus, the per-node message complexity is O(1). ◀

4

The Generalized Tree-Intersection Framework

To achieve a dramatic speedup in time complexity, at the expense of per-node message complexity, we generalize the “path-intersection” concept into a “tree-intersection” strategy. Instead of sending a single token on a random walk, each candidate initiates an ℓ-ary tree √ expansion of size 2 × ⌈ n log n⌉, which ensures that trees encounter one another w.h.p.

4.1

An Informal Description of the Tree-Intersection Strategy

1. Trading bandwidth for time. The advantage of the path-intersection approach is the low per-node message complexity, its core limitation is its sequential nature. By instructing each node to forward the rank to ℓ neighbors instead of just one, we transform the linear walk into a tree. This allows us to cover the same “footprint” required for intersection in √ O(logℓ n log n) rounds (for ℓ ≥ 2). For a binary tree (ℓ = 2), this is logarithmic time; for larger branching factors, it collapses toward constant time. 2. The all-back verification principle. While the “Birthday Paradox” ensures intersection between every two trees, it does not guarantee that every path will intersect with the global maximum. We address this issue as follows. A candidate is elected only if it √ receives acknowledgments from all the N = 2 × ⌈ n log n⌉ (logical) nodes generated. If a branch encounters a node already dominated by a higher rank, that branch is “pruned”.

10

Randomized Tree-Intersection Leader Election

Crucially, at least the node at which the intersection happens sends no acknowledgment to the lower rank candidate. This prevents a lower rank candidate from accumulating the necessary number of acknowledgments to become a leader. 3. Handling internal collisions. A subtle challenge arises because we select neighbors randomly (with replacement): a tree might loop back on itself, or two branches might converge on the same node. When a node is reached by multiple (say x > 1) parents of the same tree in a given round (an internal collision), it treats only the first one as its true parent for this round, sets its own weight to x, and sends explore messages to ℓ × x of its neighbors. Later when ACKs arrive, the node reports the aggregated sum of the ACKs plus its own weight x to the single true parent. This ensures that the total weight reported to the highest ranked candidate matches the target weight N . 4. The silent pulse optimization. Because the tree grows layer-by-layer, every parent knows exactly when to expect an ACK from its children. If a parent hears nothing from a child in the expected round, it assumes that child was a duplicate branch (i.e., an internal collision) handled by someone else, or a pruned branch. This allows us to eliminate explicit “I am a duplicate” messages, relying instead on the “conservation of weight” carried by the active branches. 5. Satisfying the CONGEST constraint. Every node in the graph stores and propagates only the messages (both Explore and ACK) of the highest rank it has seen, effectively pruning branches of all but the most dominant tree as the expansions collide. The Explore and ACK messages have three counters associated with them and as we prove, each one of these counters require at most O(log n) bits to encode. 6. Optimizing tree volume via almost complete tree expansion. A naive implementation of the ℓ-ary expansion might force the algorithm to construct a perfect ℓ-ary tree (because of the simple stopping condition). However, this introduces an undesirable multiplicative overhead: the final level could contain up to a factor of ℓ more nodes compared to the √ desired volume of 2 × ⌈ n log n⌉, blowing up the total message complexity by a factor of ℓ. To prevent this volume explosion, our framework constructs an almost complete ℓ-ary tree. The expansion halts dynamically so that the total number of (logical) nodes is exactly √ 2 × ⌈ n log n⌉. Implementing the exact stopping condition so that the expansion “knows” when to halt is one of the key ideas of our design, and is explained in Subsection 4.2.

4.2

How the almost-complete tree is constructed

To avoid the multiplicative volume overhead of a perfect ℓ-ary tree, our algorithm dynamically truncates the tree’s expansion. We achieve this by allowing physical network nodes to concurrently simulate multiple independent logical tree nodes, only compressing their data into bundled physical transmissions when random draws route them over the same communication link. By logical tree we mean the conceptual tree constructed by a candidate. If two branches converge on the same physical node, this physical node hosts multiple distinct logical nodes. The construction builds a logical almost complete ℓ-ary tree with N logical nodes. √  Let N = 2 n log n be the exact target volume of the logical tree, and let 1 ≤ ℓ ≤ N be the branching parameter. For any integer h ≥ 0, let Th be the volume of a perfect ℓ-ary tree of h+1 height h. That is, if ℓ = 1, then Th = h+1, and if ℓ ≥ 2, then Th = 1+ℓ+ℓ2 +· · ·+ℓh = ℓ ℓ−1−1 . The Core Tree and the Leaf Budget. We define H as the maximum integer h ≥ 0 such that Th < N . If ℓ = 1, then H = N − 2, and if ℓ ≥ 2, then H = ⌈logℓ ((ℓ − 1)N + 1)⌉ − 2. The perfect ℓ-ary tree of height H is called the core tree. To reach exactly N total nodes, we must add an exact number of leaves at the last level below the core tree. We define this

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

remaining requirement as the node’s initial budget: Leaf(ℓ, N ) := N − TH . Token Bundling and Budget Distribution. Random walks may cause multiple branches of the same candidate’s logical tree to collide at a single physical node v. If v hosts t logical nodes belonging to the same candidate at core depth d, it also holds an aggregated budget x representing the total number of leaves at the last level those t tokens are allowed to spawn. The construction begins at the root, which hosts exactly one depth-0 logical node (t = 1), with initial budget x = Leaf(ℓ, N ) = N − TH . To continue the expansion while respecting CONGEST constraints, v must simulate the next step for all t tokens. If the expansion is still within the core tree (0 ≤ d < H), v generates ℓ · t logical children. Each hosted depth-d logical node becomes the logical parent of exactly ℓ of these children, and each such child has depth d + 1. Each of the newly generated ℓ · t children corresponds to an independent random draw (with replacement) from the physical neighbors of v. Node v partitions the total budget x sequentially among these ℓ · t draws. Each draw is assigned the maximum capacity of ℓH−d as long as sufficient budget remains. If the remaining budget is positive but strictly less than ℓH−d , the next draw receives this exact remainder, and all subsequent draws are assigned a budget of 0. Crucially, physical bundling occurs at the outbound edge level based on these random draws. If a specific physical neighbor u is selected k times during the draws, v bundles these k logical children into a single physical message sent to u. This bundled message carries the candidate’s rank, the token count k, and the sum of the specific leaf budgets assigned to those k draws. If the expansion has reached the boundary of the core tree (d = H) at a physical node v that hosts t depth-H logical nodes and has budget x, then the t logical nodes do not spawn full branches. Instead, v partitions the total budget x sequentially among these t nodes. Each hosted logical node becomes the logical parent of ℓ leaves at the last level as long as sufficient budget remains. If the remaining budget is positive but strictly less than ℓ, the next hosted logical node receives this exact remainder, and all subsequent hosted logical nodes receive 0 budget. Overall, v creates exactly x leaves at the last level (each with budget 0) for its hosted logical nodes. Each leaf at the last level is then placed by an independent random draw from the physical neighbors of v, again bundling tokens and their respective budgets into single physical messages if the same physical neighbor is drawn multiple times. Message Complexity Overhead. Because the network size n and parameter ℓ are globally known, the structural constants N , H, and the initial budget can be computed locally by all nodes. The global synchronous clock provides the current depth d. Therefore, the only dynamic state a bundled physical message must transmit across any specific edge is the candidate’s rank, the subset of logical tokens routed over that edge (e.g., k), and the sum of the specific leaf budgets assigned to those k draws. Because the total number of logical tokens in the entire √ treeand the maximum total budget never exceed N , these counters are bounded by 2 n log n , and require at most O(log n) bits.

4.3

The Algorithm

We first define the structure of the two primary message types utilized during the tree expansion and verification phases before presenting Algorithm 2. EXPLORE Message: Formatted as ⟨EXPLORE, rmax , bundle, budget⟩. rmax : The highest candidate rank observed by the sending node.

11

12

Randomized Tree-Intersection Leader Election

bundle: The number of independent logical tokens traversing the exact same physical edge in this round, bundled together to conserve bandwidth. budget: The specific portion of the leaf-allocation budget assigned to these bundled tokens, dictating how many leaves at the last level they are permitted to spawn. ACK Message: Formatted as ⟨ACK, rmax , weight⟩. rmax : The dominant candidate rank being acknowledged. weight: The aggregated sum of valid logical nodes, including the sender’s own logical presence and the returning acknowledgments from its children. The Dual Role of the explore_cnt Array. We highlight how the explore_cnt array shifts its purpose between the algorithm’s primary phases. During Phase 2, explore_cnt[i] acts strictly as a collision counter. It records the total number of highest-ranked logical tokens that converged on the physical node during round i. During Phase 3, this array transitions into a topological weight accumulator. The node initially treats its stored explore_cnt[i] value as its own base weight at round i. As ACK messages return at round i from its neighbors, the node aggregates their reported weights directly into its explore_cnt[i]. This effectively rolls up the total volume of the node’s subtree at round i.

4.4

Correctness and Analysis of Algorithm 2

We first formalize two invariants of the algorithm: the timing invariant that proves when the ACK messages arrive, and the conservation of weight invariant regarding the exact preservation of logical weight despite internal collisions. ▶ Lemma 7 (Timing Invariant of the Silent Pulse). For any node v that adopts a candidate’s rank rmax at round d (1 ≤ d ≤ H + 1) of Phase 2, v receives all valid ACK tokens from its spawned children precisely in round H + 1 − d of Phase 3. The absence of an ACK in this round safely evaluates to an implicit weight of zero. Proof. During Phase 2, if v receives and adopts the maximum rank token at round d, it records the arrival edge as parent[d] and forwards EXPLORE tokens to its chosen neighbors at round d + 1. A neighbor u that successfully receives this token will record the arrival edge as parent[d + 1]. During Phase 3, which executes for rounds i = 1 to H + 1, a node sends its accumulated weight via the edge parent[H − i + 2]. Node u will therefore transmit its ACK back to v when H − i + 2 = d + 1. Because the network is strictly synchronous, v evaluates and aggregates all incoming ACKs exactly in round i = H − d + 1. Because v expects and processes ACKs from its children strictly in round H − d + 1, any branch that was pruned (due to encountering a higher rank) or absorbed (due to an internal collision) naturally drops out of the communication flow. By treating non-arriving messages as 0 weight, the algorithm eliminates the need for explicit rejection messages while strictly preserving the layer-by-layer temporal structure of the tree. ◀ ▶ Lemma 8 (Conservation of Weight). Let vmax be the candidate with the unique global maximum rank rankmax . In Phases 1&2 (1) the sum of explore_cnt[i] across all nodes at the end of round 0 ≤ i ≤ H is exactly ℓi , and (2) the sum of explore_cnt[H + 1] across all nodes at the end of round H + 1 is exactly N − T (ℓ, N ) (i.e., # of leaves at the last level) Consequently, in Phase 3, the total weight returned to vmax in round 2H + 2 equals N (i.e., the total number of EXPLORE tokens with the highest rank submitted plus one). Proof. For 0 ≤ i ≤ H, we proceed by induction on the round number i in Phases 1&2. Base case (i = 0): Candidate vmax initializes explore_cnt = 1, which trivially equals ℓ0 . Inductive step: Assume the sum of explore_cnt across all nodes at round i − 1 is ℓi−1 . In

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

Algorithm 2 Tree-Intersection Leader Election in Complete Graphs The following code is executed by each node v ∈ V Constants (known to all nodes): G = (V, E)√where |V | = n ▷ G is a complete graph N = 2 × ⌈ n log n⌉ ▷ samples volume used for Birthday Paradox ℓ = Branching factor (ℓ ≥ 1) ▷ ℓ = 1 for Walk, ℓ ≥ 2 for Tree T (ℓ, N ▷ core tree ) = maximum integer of size < N , for which there is a perfect ℓ-ary tree N −2 if ℓ = 1 H= ▷ height of the core tree with volume T (ℓ, N ) < N ⌈logℓ ((ℓ − 1)N + 1)⌉ − 2 if ℓ ≥ 2 State variables at node v: ▷ H + 1 (not H) is the height of the ℓ-ary tree rv ← 0, rmax ← 0, parent[1..H + 1] ← ⊥ ▷ rv = rank of v, rmax = dominant rank discovered explore_cnt[0..H + 1] ← 0 ▷ for each round, counts # of highest rank incoming EXPLORE tokens bundle_cnt ← 0 ▷ a branch may be selected more than once during draws budget_sum ← 0 ▷ # of leaves to be spawn at the last level B ← ∅; M ← ∅; A ← ∅ ▷ B multiset of edges, M & A sets of EXPLORE msgs, ACK msgs Phase 1: Candidate Selection (Round 0) 1: Node v independently becomes a candidate with probability p = logn n 2: if v is a candidate then 3: rv ← generate a random rank from {1, . . . , n4 } ▷ unique rank w.h.p. 4: rmax ← rv ; explore_cnt[0] ← 1; budget_sum ← N − T (ℓ, N ) ▷ ready to send tokens Phase 2: Forward Tree-Expansion (Rounds 1 to H + 1) ▷ H + 1 = height of the ℓ-ary tree 5: for round i = 1 to H do ▷ for each round i, first send messages and then receive 6: if explore_cnt[i − 1] ̸= 0 then ▷ at least one token with rmax received in round i − 1 7: B ← Select ℓ × explore_cnt[i − 1] branches to neighbors u.a.r. with replacement 8: for each branch b ∈ supp(B) do ▷ sequentially; supp(B) = the set of unique elements in B 9: bundle_cnt ← # of times b appears in B ▷ bundle bundle_cnt tokens in one message 10: if budget_sum ≥ bundle_cnt · ℓH−i+1 then ▷ partitions the total budget sequentially 11: budget_temp ← bundle_cnt · ℓH−i+1 ▷ assigned the maximum capacity 12: else 13: budget_temp ← budget_sum ▷ receives remainder budget 14: budget_sum ← budget_sum − budget_temp ▷ remanning budget 15: Send ⟨EXPLORE, rmax , bundle_cnt, budget_temp⟩ via branch b ▷ EXPLORE via b 16: M ← EXPLORE tokens received in this round ▷ budget_sum = 0 at this point 17: for each ⟨EXPLORE, r, bundle, budget⟩ ∈ M do ▷ counts sequentially # of high rank tokens 18: if r > rmax then ▷ new dominant rank discovered 19: rmax ← r; parent[i] ← arrival edge from sender ▷ facilitate trace-back 20: explore_cnt[i] ← bundle; budget_sum ← budget ▷ first high rank incoming exploration 21: explore_cnt[0..i − 1] ← 0 ▷ clear history 22: else if r = rmax and parent[i] = ⊥ then ▷ loop or late arrival with same high rank 23: parent[i] ← arrival edge from sender ▷ facilitate trace-back 24: explore_cnt[i] ← bundle; budget_sum ← budget ▷ first high rank exploration in round i 25: else if r = rmax and parent[i] ̸= ⊥ then ▷ internal collision 26: explore_cnt[i] ← explore_cnt[i] + bundle; budget_sum ← budget_sum + budget 27: else drop ⟨EXPLORE, r, bundle, budget⟩ ▷ disqualified by a higher rank that arrived earlier Phase 2: Round H + 1 28: if budget_sum ̸= 0 then ▷ ready to spawn budget_sum new leaves 29: B ← Select budget_sum branches to neighbors u.a.r. with replacement 30: for each branch b ∈ supp(B) do ▷ branches to spawn 31: bundle_cnt ← # of times b appears in B ▷ bundle bundle_cnt tokens in one message 32: Send ⟨EXPLORE, rmax , bundle_cnt, 0⟩ via branch b 33: M ← EXPLORE tokens received in this round ▷ M is a set of tokens 34: for each ⟨EXPLORE, r, bundle, 0⟩ ∈ M do ▷ counts sequentially # of high rank tokens 35: if r > rmax then ▷ new dominant rank discovered 36: rmax ← r; parent[H + 1] ← arrival edge from sender ▷ facilitate trace-back 37: explore_cnt[H + 1] ← bundle; explore_cnt[0..H] ← 0 ▷ update state and clear history 38: else if r = rmax and parent[H + 1] = ⊥ then ▷ loop or late arrival with same high rank 39: parent[i] ← arrival edge from sender ▷ facilitate trace-back 40: explore_cnt[H + 1] ← bundle ▷ first high rank incoming exploration in round i 41: else if r = rmax and parent[H + 1] ̸= ⊥ then ▷ internal collision 42: explore_cnt[H + 1] ← explore_cnt[H + 1] + bundle ▷ adds bundle of high rank explorations 43: else drop ⟨EXPLORE, r, bundle, 0⟩ ▷ disqualified by a higher rank that arrived earlier

13

14

Randomized Tree-Intersection Leader Election

Algorithm 2 Tree-Intersection Leader Election in Complete Graphs (Continued) Phase 3: Trace-back and Verification (Rounds H + 2 to 2H + 2) 44: for round i = 1 to H + 1 do ▷ global rounds H + 2 to 2H + 2 45: if explore_cnt[H − i + 2] ̸= 0 then ▷ if there is an ACK to send 46: Send ⟨ACK, rmax , explore_cnt[H − i + 2]⟩ via edge parent[H − i + 2] 47: A ← ACKs received in this round 48: for each ⟨ACK, r, weight⟩ ∈ A do ▷ aggregates weights returned by children + own weight 49: if r = rmax then explore_cnt[H − i + 1] ← explore_cnt[H − i + 1] + weight 50: else drop ⟨ACK, r, weight⟩ ▷ disqualified by a higher rank that arrived later Phase 4: Termination (Round 2H + 3) 51: if v is a candidate and explore_cnt[0] = N then ▷ rv = rmax 52: status ← LEADER else status ← NOT_LEADER

round i exactly ℓ × ℓi−1 = ℓi EXPLORE tokens with rankmax are transmitted in the network. Because no rank in the network is strictly greater than rankmax , no node drops these tokens. If multiple tokens arrive at the same node, this node aggregates them by incrementing explore_cnt[i] for each token. Thus, the sum of explore_cnt at round i is exactly ℓi . As for round H + 1, exactly N − T (ℓ, N ) EXPLORE tokens with rankmax are transmitted, and each node upon receiving one of these token will increment by one explore_cnt[H + 1]. In Phase 3, governed by the layer-by-layer retracing established in Lemma 7, this aggregated weight is passed back without loss. The precise timing ensures no race conditions occur during weight aggregation, ensuring the sum of all weights returned to vmax equals the number of EXPLORE tokens with rankmax submitted plus one (the root) which is N . ◀ The following technical lemma is used in the proofs of Lemma 10 and Lemma 14. ▶ Lemma 9 (The Almost Complete Tree Construction). For every n ≥ 2 and every integer 1 ≤ ℓ ≤ N , the construction described in Section 4.2 (as implemented in Algorithm 2) produces an almost complete ℓ-ary logical tree with exactly N logical nodes. That is, for every depth 0 ≤ d < H, each logical node of depth d has exactly ℓ logical children, and every logical node of depth H has at most ℓ logical children. The number of supplementary leaves (at the last level) added to the core tree, namely at depth H + 1, is the initial budget Leaf(ℓ, N ). A detailed proof of Lemma 9 appears in Appendix A. √  ▶ Lemma 10 (Tree Intersection Probability). Let N = 2 n log n and let ℓ be the branching parameter such that 1 ≤ ℓ ≤ N . In a complete graph Kn , let T1 and T2 be two independent tree expansions generated by Algorithm 2, with the corresponding ℓ-ary logical trees T1′ and T2′ , respectively, each of exact volume N . The probability that T1 ∩ T2 = ∅ is at most n−4 . Proof. By Lemma 9, both logical trees T1′ and T2′ contain exactly N logical nodes. Let ′ X1′ , . . . , XN and Y1′ , . . . , YN′ be the logical nodes of T1′ and T2′ , respectively, ordered in BFS order, where X1′ and Y1′ are the roots. For every i ∈ [N ], let Xi (resp., Yi ) be the physical node reached by the token corresponding to Xi′ (resp., Yi′ ). Then T1 and T2 are exactly the sets {X1 , . . . , XN } and {Y1 , . . . , YN }, respectively. The rest of the proof is the same as the proof of Lemma 1, with the following minor difference. In Lemma 1, for every j ≥ 2, the node Yj is sampled from Yj−1 . Here, Yj is sampled from the physical node corresponding to the logical parent of Yj′ , which appears earlier in the BFS order, but is not necessarily Yj−1 . This makes no difference, since the proof conditions on all previously exposed physical nodes Y1 , . . . , Yj−1 being outside SX = {X1 , . . . , XN }. Thus, the physical node corresponding to the logical parent of Yj′ is outside SX , and the same bound applies.

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

The same observation applies when lower-bounding the number of distinct nodes in SX . When exposing Xi in BFS order, the node Xi is sampled from the physical node corresponding to the logical parent of Xi′ , which appears earlier in the BFS order. Thus, conditioning on the previously exposed physical nodes gives the same lower bound on the probability that Xi is new as in Lemma 1. Therefore, the calculation from Lemma 1 applies verbatim and gives Pr[T1 ∩ T2 = ∅] ≤ n−4 ,for all sufficiently large n. ◀ ▶ Theorem 11 (Safety). With high probability, algorithm 2 elects at most one leader. Proof. Let vmax be the candidate with the unique maximum rank rankmax . Suppose for contradiction that another candidate u ̸= vmax with rank ru < rankmax is elected. For u to be elected, it must evaluate explore_cnt[0] = N at round 2H + 3. By Lemma 10, u’s tree expansion and vmax ’s tree expansion intersect at some node z with high probability. Because expansions proceed synchronously layer-by-layer, node z updates its local rmax to rankmax . (Any subsequent or concurrent EXPLORE or ACK token carrying ru arriving at z will trigger the “drop” condition.) Thus, node z will never send an ACK message to u. By Lemma 8, the lost weight from this unsent ACK by z is never returned to u, strictly bounding u’s final explore_cnt[0] < N . Thus, u cannot be elected. ◀ ▶ Theorem 12 (Liveness). With high probability, exactly one leader is elected. Proof. The candidate vmax possesses the global maximum rank. Therefore, its tokens can never trigger the drop condition at any node. By Lemma 8, the “silent pulse” aggregation successfully prevents weight loss during internal collisions. Consequently, vmax receives exactly N acknowledgments (by weight) in Phase 3, fulfilling the termination condition. Combined with Theorem 11, vmax is the unique leader w.h.p. ◀ ▶ Theorem 13 (CONGEST). The constraint of the CONGEST model is satisfied. Proof. Algorithm 2 utilizes two types of messages: EXPLORE and ACK, which carries a rank value. Because candidate ranks are chosen from the domain {1, . . . , n4 }, representing a rank requires exactly ⌈log2 (n4 )⌉ = 4 log2 n bits, which is O(log n). Because every node only forwards the single maximum rank it has seen, an edge carries at most one token per round. In Phase 2&3, Explore and ACK has the formats ⟨EXPLORE, rmax , bundle, budget⟩, and ⟨ACK, rmax , weight⟩. The rank rmax again takes O(log n) bits. The maximum possible values for the bundle_cnt, budget_temp and explore_cnt[i] variables is bounded by N . √ Since N ≈ 2 n log n, the number of bits required to represent these variables is at most √ ⌈log2 (2 n log n)⌉ ≈ 21 log2 n + 12 log2 (log n) + 1. This is strictly bounded by O(log n) bits. Since both the EXPLORE and ACK tokens require O(log n) bits to encode, and the pruning mechanism ensures at most one such token is sent across any specific edge in a single round, the algorithm strictly adheres to the CONGEST bandwidth constraints. ◀ ▶ Theorem 14 (Complexity Bounds). With high probability, Algorithm 2 achieves: √ √ 1. Time Complexity: O( n log n) rounds if ℓ = 1, and O(logℓ n log n) rounds if ℓ ≥ 2. √ 2. Total Message Complexity: O( n log1.5 n) messages. 3. Per-Node Message Complexity: O(ℓ) messages. √  √ Proof. Time: Let N = 2 n log n = O( n log n). The algorithm executes for 2(H + 1) √ rounds. For ℓ = 1, since H = N − 2, the time complexity is O( n log n). For ℓ ≥ 2, since H = ⌈logℓ ((ℓ − 1)N + 1)⌉ − 2 ≤ O(logℓ (2ℓN )) ≤ O(logℓ (2ℓ) + logℓ (N )) ≤ O(logℓ (N )),

15

16

Randomized Tree-Intersection Leader Election

the time complexity is O(logℓ

√

n log n).

Total Messages: As proven in Theorem 6, the number of candidates is bounded by |C| ≤ 4 log n w.h.p. By Lemma 9, the logical tree generated by each candidate has volume N . Thus, each candidate generates at most N − 1 EXPLORE messages. Therefore, the total number of EXPLORE messages over all candidates is at most |C| · (N − 1) ≤ |C| · N . Each ACK message corresponds to at least one generated EXPLORE message. Indeed, ACKs are only sent back along edges that were created by EXPLORE messages, and if several ACKs are bundled, this only decreases the number of physical ACK messages. Hence, Phase 3 generates at most the same number of messages the total  2. Therefore, √as Phase √ number of messages satisfies M ≤ 2|C|N ≤ 2 · (4 log n) · 2 n log n = O( n log1.5 n) w.h.p. Per-Node Complexity: Fix a physical node v. We first bound the number of logical EXPLORE units received by v. Let XvE denote this number. Let E be the event that |C| ≤ 4 log n. As in Theorem 6, Pr[¬E] ≤ n−3.67 . Condition on an arbitrary candidate set C such that |C| ≤ 4 log n. Order all logical EXPLORE trials in some fixed order, first by the ID of the candidate that generated the logical tree, and then by the BFS order of the logical tree. By Lemma 9, each candidate generates a logical tree of exact volume N , and therefore there are at most 4N log n logical EXPLORE trials. For the ith trial, let Ii be the indicator for the event that the corresponding logical P4N log n EXPLORE unit is received by v. Then XvE = Ii . As in the per-node proof i=1 of Theorem 6, for every history before the ith trial, the probability that the next logical EXPLORE unit is received by v is at most 1/(n−1). Indeed, if the physical node corresponding to the logical parent is v, then the probability that the next logical child is mapped to v is 0; otherwise, the next physical node is chosen uniformly among the n − 1 neighbors. Thus, conditioned on E, the random variable XvE is stochastically dominated by the random variable Bin(4N log n, 1/(n − 1)). The same calculation as in Theorem 6, with XvE in place of XvF , gives Pr[∃v ∈ V : XvE ≥ 6] ≤

1 , n

for all sufficiently large n. Thus, with probability at least 1 − 1/n, every physical node receives at most 5 logical EXPLORE units. It remains to translate this into total processed physical messages. Physical bundling can only decrease the number of messages, so it is enough to upper-bound the number of logical units processed by v. During Phase 2, every logical EXPLORE unit received by v can cause at most ℓ logical EXPLORE units to be sent by v, because every logical node has at most ℓ children by Lemma 9. In addition, v may send at most ℓ initial logical EXPLORE units if it is a candidate. Hence, the number of EXPLORE units sent by v is at most ℓXvE + ℓ. During Phase 3, every ACK unit sent by v corresponds to a logical EXPLORE unit previously received by v. Thus, the number of ACK units sent by v is at most XvE . Similarly, every ACK unit received by v corresponds to a logical EXPLORE unit previously sent by v. Therefore, the number of ACK units received by v is at most ℓXvE + ℓ. Consequently, the total number of logical units processed by v is at most XvE + (ℓXvE + ℓ) + XvE + (ℓXvE + ℓ) = (2ℓ + 2)XvE + 2ℓ. Since, with probability at least 1 − 1/n, we have XvE ≤ 5 for every node v, every node processes at most (2ℓ + 2) · 5 + 2ℓ = 12ℓ + 10 = O(ℓ) messages. Thus, the per-node message complexity is O(ℓ). ◀

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

5

Related Work

Symmetry breaking and leader election (LE) are among the most extensively studied problems in distributed computing. A critical nuance in the history of the LE problem is the distinction between explicit and implicit LE. In the explicit version, every node must terminate knowing the identifier of the elected leader. This requirement naturally leads to a message complexity of Ω(n), as the leader’s identity must be disseminated to every node. Early research focused heavily on solving deterministically the explicit version in the asynchronous model. The seminal work of Gallager, Humblet, and Spira (GHS) [3] established a foundational baseline for general graphs, achieving O(m + n log n) total messages and O(n log n) time for minimum spanning tree construction and explicit LE in general graphs, where m is the number of edges. The Ω(n log n) term represents the inescapable cost of deterministic symmetry breaking, as first demonstrated on the ring topology [1, 12]. The lower bounds Ω(m) (and Ω(D) for time complexity, where D is the diameter), were proven in [8], and hold also for randomized algorithms in the synchronous model. To achieve sublinear message complexity, two shifts were necessary: the introduction of randomization and the move toward implicit LE. Recent advancements in the study of implicit LE have focused on optimizing total message complexity and execution time. Kutten et al. [9] introduced a synchronous randomized algorithm with sublinear total message √ complexity, and an almost matching lower bound showing that Ω( n) messages are needed for any randomized LE algorithm that succeeds with probability at least 1/e + ϵ, for any small constant ϵ > 0. The approach of [9] inherently requires high local bandwidth (a massive concurrent broadcast). Our work is the first to parameterize and optimize the per-node message complexity while maintaining strictly sublinear total communication. In [4], a randomized synchronous algorithm is presented that solves implicit LE in a √ general network G with O(tmix (G) · n log3.5 n) messages and in O(tmix (G) · log2 n) time, but has high local per-node message complexity. Correspondingly, a nearly matching lower √ bound is presented, showing that Ω( n)/(ϕ)3/4 messages are needed for any implicit LE algorithm that succeeds with probability at least 1 − o(1), where ϕ refers to the conductance of a graph. A key difference between [4] and [9] is that in [4] it is not assumed that the mixing time is known, which significantly complicates the problem. In [5], a randomized synchronous algorithm is presented that solves LE in general network p G with O(min{ n · tmix (G)/ϕ, n/(ϕ log n)}) messages and O(tmix (G) log n + ϕ−1 log3 n) time assuming the conductance and the mixing time are known. As for asynchronous complete graphs, a randomized LE algorithm that achieves sublinear n log1.5 n message complexity w.h.p. and O(log n) time complexity, but has high local per-node bandwidth, was presented in [2]. √

6

Discussion

Leader election in general graphs. In Section 4, we established the tree-intersection strategy for complete graphs, where a single random hop from any node results in a perfectly uniform sample from the entire network. In a general graph, this property no longer holds; a single hop moves a message only to a direct neighbor, keeping the exploration strictly localized. It is tempting to adapt Algorithm 2 by introducing a logical-to-physical mapping of the tree structure. The core idea is to treat every logical edge as a physical random walk

17

18

Randomized Tree-Intersection Leader Election

of length tmix (G) – the mixing time of G.8 In such a stretched tree, a candidate initiates ℓ independent random walks. Only after tmix (G) physical rounds do the endpoints of these walks act as “logical children” and branch out into another ℓ random walks each. While conceptually elegant, formalizing this intuition is highly non-trivial. Unlike the complete graph where the stationary distribution is uniform, random walks in general graphs converge to a distribution proportional to node degrees (π(v) = d(v) 2m ). This skew means that dense areas of the graph are sampled disproportionately, which heavily alters the intersection dynamics and complicates the Birthday Paradox bounds. Furthermore, one must carefully untangle the probabilistic correlations introduced by the branching nature of the walks. Such a transformation decouples the graph’s topology from the intersection probability. Since we replace every logical round with tmix (G) physical rounds, the time complexity √ scales to O(tmix (G) · logℓ n log n) for ℓ ≥ 2, and the total message complexity scales to √ O(tmix (G) · n log1.5 n). However, while this transformation successfully achieves sublinear total message complexity, the per-node message complexity would degrade, potentially scaling as high as the total message complexity itself. This theoretical wall arises inevitably in graphs with severe structural bottlenecks. Consider a double star graph: even if we simulate logical tree expansions using random walks, one of the two center nodes lies on every path of length greater than one. Therefore, if the algorithm requires a total message complexity of M to ensure tree intersection, the center nodes are forced to process Ω(M ) messages. In such topologies, the maximum per-node message complexity binds to the total message complexity, rendering our algorithmic dial, ℓ, entirely ineffective at balancing the local communication load. Our central contribution. We presented a generalized framework for randomized implicit leader election in synchronous complete graphs under the CONGEST model. Our central contribution is the branching factor ℓ, which allows system designers to smoothly navigate √ the trade-off between time complexity (O(logℓ n log n) for ℓ ≥ 2) and per-node message complexity (O(ℓ)), while maintaining a strictly sublinear total message complexity. This framework unifies and generalizes previous state-of-the-art bounds, demonstrating that singlepath intersections and massive concurrent broadcasts are merely two extremes of the same algorithmic spectrum. Per-node complexity vs. per-edge complexity. As motivated in the Introduction, a natural consequence of our framework is its inherent guarantee regarding total per-edge message complexity. While the CONGEST model naturally prevents per-round link congestion, our total per-node bound provides a structural guarantee over the lifetime of the algorithm. For instance, an algorithm where a high-degree node sends exactly one message per incident edge keeps the total per-edge complexity minimal, yet allows the total per-node complexity to scale prohibitively with the node’s degree. By optimizing the per-node metric instead, our framework ensures that no single node is exhausted and, as a direct corollary, no single communication link is overwhelmed during the entire algorithm. Open questions. Several compelling open questions remain for future investigation:

8

The mixing time, tmix (G), of an n-node graph G, is defined as the number of steps required for the random walk distribution to get 1/(2n)-close to the stationary distribution π, with respect to the maximum norm, regardless of the starting node.

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

19

Beyond Complete Graphs: Establishing a parameterized trade-off between time and per-node message complexity for broader graph classes, such as regular graphs, remains a compelling direction for future research. Parameterized Lower Bounds: An immediate question is whether the trade-off established by ℓ is strictly optimal. Deriving a matching parameterized lower bound would prove that this latency-bandwidth exchange is an inherent property of symmetry breaking. Fault Tolerance: Extending our algorithm to be robust against node crashes or link failures would be valuable. Explicit Leader Election: Coupling our symmetry-breaking mechanism, which already maintains low per-node complexity, with an efficient broadcast protocol could yield highly optimized results for the explicit variant of the problem.

A

Proof of Lemma 9

Section 4.2 presents two definitions of H: an explicit formula and a maximum feasible height. In Lemma 15, we use the explicit formula definition and show that it is well defined and equivalent to the maximum definition. ▶ Lemma 15. The value H, namely H = N − 2 if ℓ = 1, and H = ⌈logℓ ((ℓ − 1)N + 1)⌉ − 2 if 2 ≤ ℓ ≤ N , satisfies the following properties for every n ≥ 2: 1. H is well defined. That is, when 2 ≤ ℓ ≤ N , the logarithm is taken with a valid base and over a strictly positive input. 2. H ≥ 0. 3. The set {h ∈ Z≥0 | Th < N } is a nonempty bounded integer set. That is, the maximum integer h ≥ 0 such that Th < N is well defined. Moreover, H is exactly that maximum, and TH < N ≤ TH+1 . √  Proof. Since N = 2 n log n , for n ≥ 2, we have N ≥ 2. Let H := {h ∈ Z≥0 | Th < N }. h→∞

For both ℓ = 1 and ℓ ≥ 2, we have T0 = 1 < 2 ≤ N . Thus, H = ̸ ∅. Since Th −→ ∞, there exists an integer M such that for every h ≥ M , we have Th ≥ N . Therefore, every h satisfying Th < N must satisfy h < M , so the set H is bounded. Since it is also nonempty, it has a maximum. Therefore, max H, (i.e., the maximum integer h ≥ 0 such that Th < N ) is well defined. First, suppose that ℓ = 1. Then H = N − 2 is well defined. Also, since N ≥ 2, we have H ≥ 0. Moreover, Th = h + 1. Thus, Th < N is equivalent to h + 1 < N . Since N is an integer, this is equivalent to h ≤ N − 2. Therefore, the maximum such integer is indeed H = N − 2. Moreover, TH = H + 1 = N − 1 < N = H + 2 = TH+1 , so TH < N ≤ TH+1 . Now suppose that 2 ≤ ℓ ≤ N . Let A := logℓ ((ℓ − 1)N + 1). First, A is well defined. Indeed, since ℓ ≥ 2, the base of the logarithm is valid. Moreover, since 2 ≤ ℓ ≤ N , we have (ℓ − 1)N + 1 = ℓN − N + 1 ≥ 2N − N + 1 = N + 1 ≥ ℓ + 1 > ℓ > 0.

(1)

20

Randomized Tree-Intersection Leader Election

Thus, A = logℓ ((ℓ − 1)N + 1) is well defined. The proposed value is H = ⌈A⌉ − 2. We show that H ≥ 0. By Inequality (1), we have (ℓ − 1)N + 1 > ℓ. Therefore, since ℓ ≥ 2 and logℓ (x) is strictly monotonically increasing in x > 0, we have A > logℓ (ℓ) = 1. Thus, ⌈A⌉ ≥ A > 1. Since ⌈A⌉ is an integer, ⌈A⌉ ≥ 2. Hence, H = ⌈A⌉ − 2 ≥ 0. We now show that TH < N . Since ⌈A⌉ − 1 < A, we have H + 1 = ⌈A⌉ − 1 < A. Therefore, ℓH+1 < ℓA = (ℓ − 1)N + 1. It follows that TH =

ℓH+1 − 1 < N. ℓ−1

We next show that TH+1 ≥ N . Since ⌈A⌉ ≥ A, we have H + 2 = ⌈A⌉ ≥ A. Therefore, ℓH+2 ≥ ℓA = (ℓ − 1)N + 1. It follows that TH+1 =

ℓH+2 − 1 ≥ N. ℓ−1

Thus, TH < N ≤ TH+1 . Moreover, Th is increasing in h: for ℓ = 1, we have Th+1 − Th = 1 > 0, and for ℓ ≥ 2, we have Th+1 − Th = ℓh+1 > 0. This proves that H is exactly the maximum integer h ≥ 0 such that Th < N . ◀ Section 4.2 describes the tree expansion, including how budgets are partitioned during the core-tree expansion and how the supplementary leaves are assigned at the boundary of the core tree. We now make these two partition rules explicit, as they will be used in the proofs below. First, consider a physical node v that hosts t logical nodes belonging to the same candidate at core depth d, where 0 ≤ d < H, and has total budget x for these depth-d logical nodes. As described in Section 4.2, the node creates ℓ · t logical children of depth d + 1. Each hosted logical node is the logical parent of exactly ℓ of these children. The budget x is split among these ℓ · t logical children as follows. Order the ℓ · t children arbitrarily as children 1, . . . , ℓ · t. For the jth child, where 1 ≤ j ≤ ℓ · t, set xj , the budget assigned to the jth child, to be xj = min{ℓH−d , max{0, x − (j − 1)ℓH−d }}. Second, consider a physical node v that hosts t logical nodes belonging to the same candidate at core depth H, and has total budget x for these depth-H logical nodes. As described in Section 4.2, the budget x is partitioned among these t hosted logical nodes, and the resulting values determine how many supplementary leaves each hosted logical node creates. Order the t hosted depth-H logical nodes arbitrarily as nodes 1, . . . , t. For the jth hosted logical node, where 1 ≤ j ≤ t, set yj , the number of supplementary leaves assigned to the jth hosted logical node, to be yj = min{ℓ, max{0, x − (j − 1)ℓ}}.

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

21

The jth hosted logical node is the logical parent of exactly yj supplementary leaves. Next, in Lemma 16, we verify that the construction has the claimed properties in the degenerate branching case ℓ = 1. Intuitively, in this case, the core tree is simply a path, and the construction adds one final leaf to obtain exactly N logical nodes. ▶ Lemma 16. For every n ≥ 2 and ℓ = 1, the construction as described in Section 4.2 (as implemented in Algorithm 2) produces an almost complete ℓ-ary logical tree with exactly N logical nodes. That is, for every depth 0 ≤ d < H, each logical node of depth d has exactly ℓ logical children, and every logical node of depth H has at most ℓ logical children. The number of supplementary leaves added to the core tree, namely at depth H + 1, is exactly the initial budget Leaf(ℓ, N ). Proof. By Lemma 15, H ≥ 0. So our core tree height is well defined (it may include only the root, when H = 0). By the definition of H for ℓ = 1, we have H = N − 2. By the definition of TH for ℓ = 1, we have TH = H + 1 = N − 1. By the definition of Leaf(1, N ), we get Leaf(1, N ) = N − TH = 1. Due to the branching parameter ℓ = 1, the core tree is a path of height H, and therefore contains exactly TH = H + 1 = N − 1 logical nodes. By induction, the budget is exactly 1. Indeed, the root starts with budget Leaf(1, N ) = 1. At every core depth 0 ≤ d < H, there is one hosted logical token and one logical child. The rule defining xj has only j = 1 and gives   x1 = min ℓH−d , max 0, x − (j − 1)ℓH−d = min {1, max {0, 1}} = 1, since x = 1 by induction. Thus, the budget 1 is passed along the unique path until the unique core leaf at depth H. At depth H, there is one hosted logical token and budget 1. The rule defining yj has only j = 1 and gives y1 = min {ℓ, max {0, x − (j − 1)ℓ}} = min {1, max {0, 1}} = 1. Hence, the unique core leaf creates exactly one additional leaf. Therefore, the total number of logical nodes is TH + Leaf(1, N ) = (N − 1) + 1 = N. Moreover, for every depth 0 ≤ d < H, the unique logical node of depth d creates exactly one logical child. The unique logical node of depth H creates exactly one supplementary leaf. Thus, the logical tree is an almost complete 1-ary tree. ◀ We now verify the claimed properties of the construction in the genuine branching case 2 ≤ ℓ ≤ N . Intuitively, here, the core tree is a perfect ℓ-ary tree, and the remaining Leaf(ℓ, N ) leaves are distributed using the bundled physical budget. ▶ Lemma 17. For every n ≥ 2 and every integer 2 ≤ ℓ ≤ N , the construction as described in Section 4.2 (as implemented in Algorithm 2) produces an almost complete ℓ-ary logical tree with exactly N logical nodes. That is, for every depth 0 ≤ d < H, each logical node of depth d has exactly ℓ logical children, and every logical node of depth H has at most ℓ logical children. The number of supplementary leaves added to the core tree, namely at depth H + 1, is exactly the initial budget Leaf(ℓ, N ). Proof. By Lemma 15, H is well defined, H ≥ 0. So our core tree height is well defined (it may include only the root, when H = 0). Additionally, by the same Lemma, we have TH < N ≤ TH+1 .

(2)

22

Randomized Tree-Intersection Leader Election

Therefore, 1 ≤ Leaf(ℓ, N ) = N − TH . Also, since TH+1 = TH + ℓH+1 , Equation (2) implies Leaf(ℓ, N ) = N − TH ≤ TH+1 − TH = ℓH+1 . Thus, 1 ≤ Leaf(ℓ, N ) ≤ ℓH+1 .

(3)

We prove the following invariant. For every core depth 0 ≤ d ≤ H, for every physical node v that hosts t logical tokens that correspond to the same candidate and to depth d, and has total budget x for those depth-d tokens, we have 0 ≤ x ≤ tℓH−d+1 .

(4)

We prove the invariant by induction on the core depth d. At the root, we have t = 1, d = 0, and x = Leaf(ℓ, N ). By Equation (3), x ≤ ℓH+1 = tℓH−d+1 . Thus, the invariant holds at core depth 0. Now fix a depth d, such that 0 ≤ d < H, and assume that the invariant holds at this depth. Consider a physical node v that hosts t logical tokens of depth d and has total budget x for these tokens. By the induction hypothesis, 0 ≤ x ≤ tℓH−d+1 . The construction creates ℓt logical children and assigns budgets x1 , . . . , xℓt according to   xj = min ℓH−d , max 0, x − (j − 1)ℓH−d

.

For every j, this definition gives 0 ≤ xj ≤ ℓH−d . Moreover, since x ≤ tℓH−d+1 = ℓt · ℓH−d , Pℓt the greedy assignment exhausts the entire budget. Therefore, j=1 xj = x. Each child is at depth d + 1. The budget bound required for one logical token at depth d + 1 is ℓH−(d+1)+1 = ℓH−d . Thus, every child produced by the construction satisfies the required bound before bundling. If several children arrive at the same physical node at depth d + 1, the construction bundles together the children that correspond to the same candidate and to the same depth by summing their token counts and their budgets. Suppose the incoming bundles that correspond to this candidate and to this depth are indexed by r, where bundle r contains tr logical tokens and budget xr . By the previous paragraph, each incoming bundle satisfies xr ≤ tr ℓH−d . After bundling, P P the new token count is t′ = r tr , and the new budget is x′ = r xr . Hence, x′ =

X r

xr ≤

X

tr ℓH−d = t′ ℓH−d .

r

Since H − (d + 1) + 1 = H − d, this is exactly the invariant at depth d + 1. Therefore, the invariant is preserved from depth d to depth d + 1. By induction, the invariant holds at every core depth d, for 0 ≤ d ≤ H.

Y. Emek, S. Kutten, I. Rafael, and G. Taubenfeld

23

Let us now consider the supplementary leaves added to the core tree. Suppose a physical node v hosts t logical tokens of depth H and has total budget x for these tokens. By the invariant, i.e., Equation 4, we have 0 ≤ x ≤ tℓ. The construction orders the t hosted logical tokens arbitrarily and assigns values y1 , . . . , yt according to yj = min {ℓ, max {0, x − (j − 1)ℓ}} . For every j, this definition gives 0 ≤ yj ≤ ℓ. Since x ≤ tℓ, the greedy assignment exhausts Pt the entire budget. Therefore, j=1 yj = x. The jth hosted logical token creates exactly yj additional leaf tokens. Thus, every logical token at depth H creates at most ℓ logical children. For depths d < H, the construction makes every logical token create exactly ℓ logical children. Therefore, the logical tree is an almost complete ℓ-ary tree. It remains to count the number of logical nodes. The core tree has exactly TH logical nodes. The budget-splitting rule preserves the sum of all budgets from one core depth to the next. The bundling step also preserves this sum, because budgets are only summed over tokens of the same depth. At depth H, the construction creates exactly x supplementary leaves from every physical bundle with budget x. Therefore, the total number of supplementary leaves created at depth H + 1 is exactly the initial root budget, namely Leaf(ℓ, N ). Hence, the total number of logical nodes is TH + Leaf(ℓ, N ) = TH + (N − TH ) = N. ◀ Combining the two cases ℓ = 1 of Lemma 16, and 2 ≤ ℓ ≤ N of Lemma 17, we obtain the proof of Lemma 9. ◀

24

Randomized Tree-Intersection Leader Election

References 1 2

3

4

5

6

7

8 9

10 11

12

James E. Burns. A formal model for message passing systems. Technical Report TR-91, Indiana University, 1980. Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld. Team Formation and Applications. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1– 30:25, 2025. Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems (TOPLAS), 5(1):66–77, 1983. Seth Gilbert, Peter Robinson, and Suman Sourav. Leader election in well-connected graphs. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 227–236, 2018. Dariusz R. Kowalski and Miguel A. Mosteiro. Time and communication complexity of leader election in anonymous networks. In 41st IEEE International Conference on Distributed Computing Systems, ICDCS 2021, Washington DC, USA, July 7-10, 2021, pages 449–460, 2021. Manish Kumar and Anisur Rahaman Molla. On the message complexity of fault-tolerant computation: Leader election and agreement. IEEE Transactions on Parallel and Distributed Systems, 34(4):1115–1127, 2023. Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Optimal Randomized Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:18, 2020. Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Michele Scquizzato. On the complexity of universal leader election. Journal of the ACM (JACM), 62(1):1–27, 2015. Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. Sublinear bounds for randomized leader election. Theoretical Computer Science, 561:134–143, 2015. N.A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, Inc., 1996. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, 2017. 484 pages. Jan Pachl, Ephraim Korach, and Doron Rotem. Lower bounds for distributed maximum-finding algorithms. Journal of the ACM (JACM), 31(4):905–918, 1984.

Related documents

• Counting Weight-$k$ Italian Dominating Sets on Trees and Cycles#1154731
• Network Discovery and Selection Problem#420315
• Multinomial Trees and Multinomial Percolation#167514
• Global Pollinator Conference - Programme#500299
• Infinitely many size-Ramsey numbers of $k$-uniform relaxed $\ell$-trees are not polynomial#971390