Toward Optimality: A Tighter Analysis of Message Complexity for Leader Election in Diameter-Two Networks Abhijit Sadhukhan
Adri Bhattacharya
Anisur Rahaman Molla
[email protected] Indian Statistical Institute Kolkata, India
[email protected] Indian Statistical Institute Kolkata, India
[email protected] Indian Statistical Institute Kolkata, India
arXiv:2604.18029v1 [cs.DC] 20 Apr 2026
Abstract We study the message complexity of leader election in synchronous networks of diameter two. Our main contribution is a refined analysis of the randomized algorithm proposed by Chatterjee et al. [DC, 2020]. In their work, the authors established a lower bound of Ω(𝑛) messages (𝑛 is the number of nodes in the network) and presented a randomized algorithm that elects a leader in 𝑂 (1) rounds using 𝑂 (𝑛 log3 𝑛) messages with high probability. In this paper, we improve their polylog 𝑛 gap in the message bound by providing a tighter analysis of their algorithm, reducing the message complexity to 𝑂 (𝑛 log 𝑛), while preserving the 𝑂 (1)round complexity and high-probability correctness guarantee.
Keywords distributed algorithm, leader election, randomized algorithm, message complexity, diameter-two networks
1
Introduction and Related Works
Leader election is a fundamental problem in distributed computing. In this problem, nodes in the network collectively attempt to elect a single node as their leader. Leader election serves as a building block for many other distributed tasks and has been extensively studied across a wide variety of network topologies [4, 5, 11–13]. In the implicit version of leader election [10], the elected node knows that it is the leader, while all other nodes know that they are not elected. The problem was initially studied mainly in the deterministic setting [1, 12, 13]. Recent work has explored randomized solutions and established several strong results in the randomized setting. Kutten et al. [9] presented a near-optimal sublinear algorithm for leader election in complete graphs (i.e., diameter one), which runs in 𝑂 (1) √ round and uses 𝑂 ( 𝑛 log3/2 𝑛) messages with high probability and √ also showed Ω( 𝑛) message lower bound. In general graphs with diameter three or more, Kutten et al. [8] showed a lower bound of Ω(𝑚) messages for randomized leader election and also developed an algorithm which uses 𝑂 (𝑚 log log 𝑛) messages with high probability. Gilbert et al. [3] also studied randomized algorithms for implicit leader election in well-connected general graphs and analyzed complexity bounds in terms of mixing time. For additional details and comparisons, we refer the reader to [8, 9]. For diameter-two networks, Chatterjee et al. [2] established a lower bound of Ω(𝑛) messages (𝑛 is the number of nodes in the network) together with a simple near-optimal Monte Carlo algorithm, completing the understanding of the problem up to polylog gaps between upper and lower bounds. Their proposed Monte Carlo
algorithm that works in 𝑂 (1) rounds and uses 𝑂 (𝑛 log3 𝑛) messages with high probability1 and does not assume knowledge of the network size 𝑛 or any other global parameter knowledge.
Our Contributions: In this work, we provide a tighter analysis of the randomized algorithm developed by Chatterjee et al. [2]. For the sake of completeness, we include the pseudocode in Algorithm 1. Our analysis improves the message complexity bound from 𝑂 (𝑛 log3 𝑛) to 𝑂 (𝑛 log 𝑛) with high probability. This significant improvement nearly closes the gap between the upper bound and the lower bound of Ω(𝑛). Our analysis follows the same high-level framework as the original work, including the use of degree-based bucketing and concentration bounds via the Chernoff inequality. Our improvement comes from a more refined case analysis based on the expected contribution of each degree bucket to the total message complexity. Instead of applying loose upper bounds at intermediate steps, we delay aggregation and bound the relevant sums only at the end. This finer control over intermediate terms allows us to obtain a significantly tighter overall concentration bound.
2
Model and Problem Definition
The underlying synchronous congest model follows that of Chatterjee et al. [2] and has also been used in [1, 4–7, 10]. The communication network is a connected undirected graph 𝐺 = (𝑉 , 𝐸) with |𝑉 | = 𝑛 and |𝐸| = 𝑚. Each node (processor) in 𝐺 executes an instance of a distributed algorithm in synchronous rounds. In every round, a node may send messages to its neighbors, receive messages sent in the same round, and perform arbitrary local computation. Messages are of size 𝑂 (log 𝑛) bits and constitute the only means of communication; nodes do not share memory. Each node has a unique identifier of size 𝑂 (log 𝑛) bits. All nodes are initially awake and start executing the algorithm simultaneously. This is the KT0 model [11], where nodes initially know only their own identities. In this paper, we focus on graphs with diameter 𝐷 (𝐺) = 2. Since 𝐺 has diameter two, we have 𝑛−1 ≤ 𝑚 < 𝑛 (𝑛−1) . A formal definition 2 of the leader election problem is given below. Definition 2.1 (Leader Election). Each node 𝑢 maintains a variable status𝑢 taking values from {⊥, ELECTED, NON-ELECTED} with status𝑢 = ⊥ initially. An algorithm A solves the leader election problem in 𝑇 rounds if, from round 𝑇 onward, exactly one node sets its status to ELECTED and every other node sets its status to NON-ELECTED. 1 i.e., with probability at least 1 − 1 𝑛𝑐
for some constant 𝑐 ≥ 1.
,,
Abhijit Sadhukhan, Adri Bhattacharya, and Anisur Rahaman Molla
Algorithm 1 Randomized Leader Election [2] ∈ 𝑉 independently becomes a candidate with 1+log 𝑑 probability 𝑑 𝑣 𝑣 , where 𝑑 𝑣 is the degree of node 𝑣. 2: if 𝑣 becomes a candidate then 3: 𝑣 sends its ID to all its neighbors. 4: end if 5: Each node acts as a referee for all candidate neighbors (including itself, if applicable). 6: Upon receiving IDs from candidate neighbors 𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑗 , a node 𝑤 computes min{ID(𝑣 1 ), ID(𝑣 2 ), . . . , ID(𝑣 𝑗 )}. 7: Node 𝑤 sends this minimum ID back to each of 𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑗 . 8: Each candidate node 𝑣 declares itself the leader if and only if it receives its own ID from all its neighbors. 9: Otherwise, 𝑣 declares itself a non-leader.
1: Each node 𝑣
This is the standard implicit version of the leader election problem. In the explicit version, we additionally require that every non-leader node knows the identity of the leader node. In this work we discuss on implicit leader election in diameter two network.
Since 𝑋 𝑣 is an indicator random variable, 1 + log 𝑑 𝑣 . E[𝑋 𝑣 ] = 𝑝 𝑣 = 𝑑𝑣 entire Í Í 1+log 𝑑 Hence, E 𝑀 = 2𝑑 𝑣 · 𝑑 𝑣 𝑣 = 2 (1 + log 𝑑 𝑣 ). 𝑣 ∈𝑉
𝑣 ∈𝑉
Now, since 𝑑 𝑣 ≤ 𝑛 for every 𝑣 ∈ 𝑉 , we have log 𝑑 𝑣 ≤ log 𝑛. Í Í Therefore, (1 + log 𝑑 𝑣 ) ≤ (1 + log 𝑛) = 𝑛(1 + log 𝑛). 𝑣 ∈𝑉 𝑣 ∈𝑉 entire Thus, E 𝑀 ≤ 2𝑛(1 + log 𝑛) = 𝑂 (𝑛 log 𝑛).
Concentration via Bucketing: To obtain a high-probability bound on 𝑀 entire , we follow the bucketing approach of [2]. Since the variables 𝑀𝑣 are not identically distributed (they depend on 𝑑 𝑣 ), we group nodes according to their degrees. Let, 𝑘 be an integer such that 2𝑘 −1 ≤ 𝑛 < 2𝑘 . For each integer 𝑖 such that, 1 ≤ 𝑖 ≤ 𝑘, define the bucket 𝑉𝑖 = {𝑣 ∈ 𝑉 : 2𝑖 −1 ≤ 𝑑 𝑣 < 2𝑖 }. and let 𝑛𝑖 = |𝑉𝑖 | denote the number of nodes in bucket 𝑉𝑖 . Í Again assume, 𝑌𝑖 = 𝑣 ∈𝑉𝑖 𝑋 𝑣 denote the number of candidates selected from bucket 𝑉𝑖 . We now bound the expectation of 𝑌𝑖 .
3
Message Complexity Analysis
𝑖 Lemma 3.2. For every 𝑖 ≥ 2, E[𝑌𝑖 ] ≤ 3𝑖𝑛 . 2𝑖
We present a tighter analysis of the randomized Monte Carlo leader election algorithm (cf. Algorithm 1). The algorithm runs in 𝑂 (1) rounds and succeeds with high probability (cf. Lemma 3 in [2]). In this section, we prove the following theorem.
Proof. By definition, ∑︁ ∑︁ 1 + log 𝑑 𝑣 E[𝑌𝑖 ] = E[𝑋 𝑣 ] = . 𝑑𝑣 𝑣 ∈𝑉 𝑣 ∈𝑉
Theorem 3.1. Algorithm 1 succeeds to elect a leader in 𝑂 (1) rounds with high probability, while sending 𝑂 (𝑛 log 𝑛) messages.
For any 𝑣 ∈ 𝑉𝑖 , we have 2𝑖 −1 ≤ 𝑑 𝑣 < 2𝑖 . Hence, log 𝑑 𝑣 ≤ log(2𝑖 ) = 𝑖, and 𝑑1𝑣 ≤ 2𝑖1−1 . Therefore, 1 + log 𝑑 𝑣 3𝑖 1+𝑖 ≤ 𝑖 −1 ≤ 𝑖 . 𝑑𝑣 2 2 The above relation holds for 𝑖 ≥ 2. Í 3𝑖 3𝑖 ·𝑛𝑖 Thus, E[𝑌𝑖 ] ≤ = 2𝑖 , as required. 2𝑖
𝑖
We basically provide a complete analysis of the message complexity and show that Algorithm 1 uses 𝑂 (𝑛 log 𝑛) messages with high probability. For consistency, we follow the notation of [2]. Let 𝐺 = (𝑉 , 𝐸) be an undirected graph with |𝑉 | = 𝑛. For each node 𝑣 ∈ 𝑉 , let 𝑑 𝑣 denote its degree. Each node independently becomes a candidate with probability 1+log 𝑑 𝑝 𝑣 = 𝑑 𝑣 𝑣 . Let 𝑋 𝑣 be the indicator random variable defined as ( 1 if node 𝑣 becomes a candidate, 𝑋𝑣 = 0 otherwise. Í Let 𝑋 = 𝑋 𝑣 denote the total number of candidates selected. 𝑣 ∈𝑉
Let 𝑀𝑣 denote the total number of messages sent and received by node 𝑣 during the execution of the algorithm, and let 𝑀 entire = Í 𝑀𝑣 denote the total number of messages used by Algorithm 1. 𝑣 ∈𝑉
Expectation of the Total Number of Messages: By the structure of the algorithm, if a node 𝑣 becomes a candidate, it communicates with all of its neighbors. Thus, 𝑀𝑣 = 2𝑑 𝑣 · 𝑋 𝑣 . Í Therefore, 𝑀 entire = 2𝑑 𝑣 𝑋 𝑣 . 𝑣 ∈𝑉
Taking expectation and using linearity of expectation, ∑︁ E 𝑀 entire = 2𝑑 𝑣 E[𝑋 𝑣 ]. 𝑣 ∈𝑉
𝑖
𝑣 ∈𝑉𝑖
□
High-Probability Bound on Message Complexity: This is our main technical section, where we prove that this algorithm uses 𝑂 (𝑛 log 𝑛) messages with high probability. Theorem 3.3. For large enough 𝑛, 1 Pr 𝑀 entire ≥ 𝑂 (𝑛 log 𝑛) ≤ 4 . 𝑛 Proof. Recall that for each bucket 𝑉𝑖 , ∑︁ ∑︁ 𝑌𝑖 = 𝑋 𝑣 and 𝑀𝑖 = 𝑀𝑣 . 𝑣 ∈𝑉𝑖
Since 𝑀𝑣 = 2𝑑 𝑣 𝑋 𝑣 , we have 𝑀𝑖 =
𝑣 ∈𝑉𝑖
Í
2𝑑 𝑣 𝑋 𝑣 .
𝑣 ∈𝑉𝑖
Recall that, for every 𝑣 ∈ 𝑉𝑖 , we have 2𝑖 −1 ≤ 𝑑 𝑣 < 2𝑖 . Thus, ∑︁ ∑︁ 𝑀𝑖 ≤ 2 · 2𝑖 𝑋 𝑣 = 2𝑖+1 𝑋 𝑣 = 2𝑖+1𝑌𝑖 . 𝑣 ∈𝑉𝑖
𝑣 ∈𝑉𝑖
Hence, 𝑀𝑖 ≤ 2𝑖+1𝑌𝑖 . 𝑖 We have already established that E[𝑌𝑖 ] ≤ 3𝑖𝑛 , for 𝑖 ≥ 2 (cf. 2𝑖 Lemma 3.2). Now we consider three cases based on the bucket index 𝑖, classified according to the expected number of candidates selected from
Toward Optimality: A Tighter Analysis of Message Complexity for Leader Election in Diameter-Two Networks
Consider the following set J = {𝑖 : E[𝑌𝑖 ] < log 𝑛} and Í denote 𝑀 ′′ = 𝑀𝑖 .
that bucket. In all cases we will show that the messages used by all the buckets are bounded by 𝑂 (𝑛 log 𝑛) with high probability. Here we separate the Case-I for 𝑖 = 1, because, in this proof, we use Lemma 3.2 which holds for 𝑖 ≥ 2.
𝑖∈J
Using a union bound over all such buckets (at most log 𝑛 buckets), we obtain " # ∑︁ log 𝑛 1 ′′ 𝑖+1 Pr 𝑀 ≥ 6 log 𝑛 2 ≤ 6 ≤ 5. 𝑛 𝑛 𝑖∈J
Case I: 𝑖 = 1 Since 2𝑖 −1 ≤ 𝑑 𝑣 < 2𝑖 , here 𝑑 𝑣 = 1 and hence clearly total message used by this bucket is, ∑︁ 𝑀1 = 2𝑑 𝑣 · 𝑋 𝑣 ≤ 2𝑑 𝑣 · 𝑛 1 ≤ 2𝑑 𝑣 · 𝑛 = 2𝑛
Now, observe that the bucket indices satisfy the following inequalities: 1 ≤ 𝑖 ≤ 𝑘, and 2𝑘 −1 < 𝑛 ≤ 2𝑘 . 𝑘 Í Hence, 2𝑖+1 ≤ 2𝑘+2 ≤ 8𝑛.
𝑣 ∈𝑉1
as 𝑑 𝑣 = 1 and 𝑛 1 ≤ 𝑛. Case II: 𝑖 ≥ 2 and E[𝑌𝑖 ] ≥ log 𝑛 𝑖 Let, 𝑅 = 6 · 3𝑖𝑛 . 2𝑖 𝑖 So, we have 𝑅 ≥ 6 E[𝑌𝑖 ], since E[𝑌𝑖 ] ≤ 3𝑖𝑛 . 2𝑖 Since 𝑌𝑖 is a sum of independent indicator random variables, so we can use Chernoff bound ([10, Theorem 4.4(3)]) and hence we get,
𝑖=1
Therefore, Pr[𝑀 ′′ ≥ 48𝑛 log 𝑛] ≤ 𝑛15 . Combining all cases, we have the total message complexity as follows. ∑︁ ∑︁ 𝑀′ = 𝑀𝑖 , 𝑀 ′′ = 𝑀𝑖 , 𝑀 entire = 𝑀1 + 𝑀 ′ + 𝑀 ′′ . 𝑖∈I
Pr[𝑌𝑖 ≥ 𝑅] ≤ 2−𝑅 −6·3𝑖𝑛𝑖 6 · 3𝑖𝑛𝑖 ] ≤ 2 2𝑖 . ⇒ Pr[𝑌𝑖 ≥ 𝑖 2 𝑖 Since, 3𝑖𝑛 ≥ E[𝑌𝑖 ] ≥ log 𝑛 in this case, 2𝑖 −6·3𝑖𝑛𝑖 6 · 3𝑖𝑛𝑖 1 Pr 𝑌𝑖 ≥ ≤ 2 2𝑖 ≤ 2−6 log 𝑛 = 6 . 𝑖 2 𝑛
Now, 𝑀𝑖 ≤ 2𝑖+1𝑌𝑖 leads to, 6 · 3𝑖𝑛𝑖 𝑖+1 1 Pr 𝑀𝑖 ≥ · 2 ≤ 6, 2𝑖 𝑛
Let, us consider the following set I = {𝑖 : E[𝑌𝑖 ] ≥ log 𝑛}. Applying a union bound over all such buckets, and noting that the number of buckets is at most log 𝑛, we obtain " # ∑︁ ∑︁ log 𝑛 1 Pr 𝑀𝑖 ≥ 36𝑖𝑛𝑖 ≤ 6 < 5 . 𝑛 𝑛 𝑖∈I
𝑖∈J
From Case I, II, III, applying a union bound over these three events, 1 3 Pr 𝑀 entire ≥ 85𝑛 log 𝑛 ≤ 5 ≤ 4 , 𝑛 𝑛 for large enough 𝑛. Hence we conclude, 1 Pr 𝑀 entire ≥ 𝑂 (𝑛 log 𝑛) ≤ 4 , 𝑛 which completes the prove of Theorem 3.1. □
4
that is, Pr[𝑀𝑖 ≥ 36𝑖𝑛𝑖 ] ≤ 𝑛16 .
𝑖∈I
,,
Conclusion
We revisited the randomized leader election algorithm of Chatterjee et al. [2] for diameter-two networks and provided a tighter analysis of its message complexity from 𝑂 (𝑛 log3 𝑛) to 𝑂 (𝑛 log 𝑛) with high probability. Since the known lower bound is Ω(𝑛), this narrows the gap between upper and lower bounds from a log3 𝑛 factor to a single log 𝑛 factor. Closing this remaining 𝑂 (𝑛) versus 𝑂 (𝑛 log 𝑛) gap remains a challenging open problem.
Observe that, ∑︁ 𝑖∈I
𝑖𝑛𝑖 ≤
𝑘 ∑︁
𝑖𝑛𝑖 ≤
𝑖=2
𝑘 ∑︁
log 𝑛 · 𝑛𝑖 ≤ log 𝑛
𝑘 ∑︁
𝑖=2
References 𝑛𝑖 ≤ 𝑛 log 𝑛,
𝑖=2
𝑛𝑖 = 𝑛 and, 2𝑘 −1 ≤ 𝑛 < 2𝑘 . Í We conclude, Pr 𝑀𝑖 ≥ 36𝑛 log 𝑛 ≤ 𝑛15 . as we have,
Í
𝑖 ≥1
𝑖∈I
Í Let, 𝑀 ′ = 𝑀𝑖 . Then, Pr[𝑀 ′ ≥ 36𝑛 log 𝑛] ≤ 𝑛15 . 𝑖∈I Case III: 𝑖 ≥ 2 and E[𝑌𝑖 ] < log 𝑛 Let 𝑅 = 6 log 𝑛. Since E[𝑌𝑖 ] < log 𝑛, we have, 𝑅 ≥ 6E[𝑌𝑖 ]. Applying the Chernoff bound , Pr[𝑌𝑖 ≥ 6 log 𝑛] ≤ 2−6 log 𝑛 =
1 . 𝑛6
Recall that 𝑀𝑖 ≤ 2𝑖+1𝑌𝑖 . Therefore, 1 Pr 𝑀𝑖 ≥ 6 · 2𝑖+1 log 𝑛 ≤ 6 . 𝑛
[1] Yehuda Afek and Eli Gafni. 1991. Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J. Comput. 20, 2 (1991), 376–394. [2] Soumyottam Chatterjee, Gopal Pandurangan, and Peter Robinson. 2020. The complexity of leader election in diameter-two networks. Distributed Computing 33, 2 (2020), 189–205. [3] Seth Gilbert, Peter Robinson, and Suman Sourav. 2018. Leader election in wellconnected graphs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. 227–236. [4] P Humblet. 1984. Electing a leader in a clique in O (n log n) messages.(1984). Intern. Memo., Laboratory for Information and Decision Systems. [5] Ephraim Korach, Shay Kutten, and Shlomo Moran. 1990. A modular technique for the design of efficient distributed leader finding algorithms. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 1 (1990), 84–101. [6] Ephraim Korach, Shlomo Moran, and Shmuel Zaks. 1985. The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. In Proceedings of the fourth annual ACM symposium on Principles of distributed computing. 277–286. [7] Ephraim Korach, Shlomo Moran, and Shmuel Zaks. 1989. Optimal lower bounds for some distributed algorithms for a complete network of processors. Theoretical Computer Science 64, 1 (1989), 125–132. [8] Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. 2015. On the complexity of universal leader election. Journal of the ACM (JACM) 62, 1 (2015), 1–27.
,,
[9] Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. 2015. Sublinear bounds for randomized leader election. Theoretical Computer Science 561 (2015), 134–143. [10] Nancy A Lynch. 1996. Distributed algorithms. Elsevier. [11] David Peleg. 1990. Time-optimal leader election in general networks. Journal of parallel and distributed computing 8, 1 (1990), 96–99.
Abhijit Sadhukhan, Adri Bhattacharya, and Anisur Rahaman Molla
[12] Nicola Santoro. 2006. Design and analysis of distributed algorithms. John Wiley & Sons. [13] Gerard Tel. 2000. Introduction to distributed algorithms. Cambridge university press.