Toward Optimality: A Tighter Analysis of Message Complexity for Leader Election in Diameter-Two Networks Conference: ; ;

Abhijit Sadhukhan, Adri Bhattacharya, Anisur Rahaman Molla · 2026

Read Toward Optimality: A Tighter Analysis of Message Complexity for Leader Election in Diameter-Two Networks Conference: ; ; by Abhijit Sadhukhan, Adri Bhattacharya, Anisur Rahaman Molla (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18029.txt.

Introduction

Sadhukhan and two colleagues tighten message counts for leader election in synchronous diameter-two networks. Chatterjee and colleagues had shown a lower bound linear in node count. They also gave an algorithm using on the order of n log cubed n messages in constant rounds with high probability. The new analysis closes most of that polylogarithmic gap. It cuts the bound to on the order of n log n messages while preserving constant rounds and high-probability correctness.

Catalog record

CREATORAbhijit Sadhukhan, Adri Bhattacharya, Anisur Rahaman Molla
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15360
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18029

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Toward Optimality: A Tighter Analysis of Message Complexity for Leader Election in Diameter-Two Networks Conference: ; ; Abhijit Sadhukhan, Adri Bhattacharya, Anisur Rahaman Molla 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 Ω ⁡ ( n ) \Omega(n) messages ( n n is the number of nodes in the network) and presented a randomized algorithm that elects a leader in O ⁡ ( 1 ) {O}(1) rounds using O ⁡ ( n ​ log 3 ​ n ) O(n\log^{3}n) messages with high probability. In this paper, we improve their polylog ⁡ n \polylog n gap in the message bound by providing a tighter analysis of their algorithm, reducing the message complexity to O ⁡ ( n ​ log ⁡ n ) O(n\log n) , while preserving the O ⁡ ( 1 ) O(1) -round complexity and high-probability correctness guarantee. 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 ( Humblet 1984 ; Korach et al. 1990 ; Peleg 1990 ; Santoro 2006 ; Tel 2000 ) . In the implicit version of leader election ( Lynch 1996 ) , 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 ( Afek and Gafni 1991 ; Santoro 2006 ; Tel 2000 ) . Recent work has explored randomized solutions and established several strong results in the randomized setting. Kutten et al. ( Kutten et al. 2015b ) presented a near-optimal sublinear algorithm for leader election in complete graphs (i.e., diameter one), which runs in O(1) round and uses O(\sqrt{n}\log^{3/2}n) messages with high probability and also showed \Omega(\sqrt{n}) message lower bound. In general graphs with diameter three or more, Kutten et al. ( Kutten et al. 2015a ) showed a lower bound of \Omega(m) messages for randomized leader election and also developed an algorithm which uses O(m\log\log n) messages with high probability. Gilbert et al. ( Gilbert et al. 2018 ) 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 ( Kutten et al. 2015b ; Kutten et al. 2015a ) . For diameter-two networks, Chatterjee et al. ( Chatterjee et al. 2020 ) established a lower bound of \Omega(n) messages ( n 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 O(1) rounds and uses O(n\log^{3}n) messages with high probability 1 1 1 i.e., with probability at least 1-\frac{1}{n^{c}} for some constant c\geq 1 . and does not assume knowledge of the network size n 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. ( Chatterjee et al. 2020 ) . For the sake of completeness, we include the pseudocode in Algorithm 1 . Our analysis improves the message complexity bound from O(n\log^{3}n) to O(n\log n) with high probability. This significant improvement nearly closes the gap between the upper bound and the lower bound of \Omega(n) . 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. ( Chatterjee et al. 2020 ) and has also been used in ( Lynch 1996 ; Afek and Gafni 1991 ; Humblet 1984 ; Korach et al. 1990 ; Korach et al. 1985 ; Korach et al. 1989 ) . The communication network is a connected undirected graph G=(V,E) with |V|=n and |E|=m . Each node (processor) in G 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 O(\log n) bits and constitute the only means of communication; nodes do not share memory. Each node has a unique identifier of size O(\log n) bits. All nodes are initially awake and start executing the algorithm simultaneously. This is the KT0 model ( Peleg 1990 ) , where nodes initially know only their own identities. In this paper, we focus on graphs with diameter D(G)=2 . Since G has diameter two, we have n-1\leq m<\frac{n(n-1)}{2} . A formal definition of the leader election problem is given below. Definition 2.1 (Leader Election). Each node u maintains a variable \mathit{status}_{u} taking values from \{\perp,\textsc{ELECTED},\textsc{NON-ELECTED}\} with \mathit{status}_{u}=~\perp initially. An algorithm \mathcal{A} solves the leader election problem in T rounds if, from round T onward, exactly one node sets its status to ELECTED and every other node sets its status to NON-ELECTED . 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. 3. Message Complexity Analysis Algorithm 1 Randomized Leader Election ( Chatterjee et al. 2020 ) 1: Each node v\in V independently becomes a candidate with probability \frac{1+\log d_{v}}{d_{v}}, where d_{v} is the degree of node v . 2: if v becomes a candidate then 3: v 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 v_{1},v_{2},\dots,v_{j} , a node w computes \min\{\text{ID}(v_{1}),\text{ID}(v_{2}),\dots,\text{ID}(v_{j})\}. 7: Node w sends this minimum ID back to each of v_{1},v_{2},\dots,v_{j} . 8: Each candidate node v declares itself the leader if and only if it receives its own ID from all its neighbors. 9: Otherwise, v declares itself a non-leader. We present a tighter analysis of the randomized Monte Carlo leader election algorithm (cf. Algorithm 1 ). The algorithm runs in O(1) rounds and succeeds with high probability (cf. Lemma 3 in ( Chatterjee et al. 2020 ) ). In this section, we prove the following theorem. Theorem 3.1. Algorithm 1 succeeds to elect a leader in O(1) rounds with high probability, while sending O(n\log n) messages. We basically provide a

Read the complete text