The complexity of leader election in diameter-two networks

This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1–7:27, 2015) showed a fundamental lower bound of \(\varOmega (m)\) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability; this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., graphs with diameter one), Kutten et al. (Theor Comput Sci 561(Part B):134–143, 2015) established a tight bound of \(\tilde{\varTheta }(\sqrt{n})\) on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known. In this paper, we settle this complexity by showing a tight bound of \(\tilde{\varTheta }(n)\) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least \(1 - n^{-c}\), for some fixed positive constant c) succeeds and uses \(O(n\log ^3{n})\) messages and runs in O(1) rounds; this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs \(\varOmega (n)\) messages (even when n is known), regardless of the number of rounds. We also present an \(O(n\log {n})\) message deterministic algorithm that takes \(O(\log {n})\) rounds (but needs knowledge of n); we show that this message complexity is tight for deterministic algorithms. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-à-vis the graph diameter.

1. Throughout, “with high probability” means with probability at least \(1 - n^{-c}\), for some fixed positive constant c.

2. Afek and Gafni [1] show the \(\varOmega (n\log {n})\) message lower bound for complete networks under the non-simultaneous wakeup model in synchronous networks. As we have verified in our private communications with Shay Kutten (Professor, Technion), the same message bound can be shown to hold in the simultaneous wake-up model as well under the restriction that the number of rounds is bounded by a function of n.

3. We point out that lower bounds for complete networks do not directly translate to diameter-two networks.

4. If one assumes the KT1 model, where nodes have an initial knowledge of the IDs of their neighbors, there exists a trivial algorithm for leader election in a diameter-two graph that uses only O(n) messages.

5. This lower bound assumes non-simultaneous wakeup though. If nodes are assured to wake up at the same time in synchronous complete networks, there exists a trivial algorithm: if a node’s identity is some i, it waits i time before it sends any message then leader election could be solved (deterministically) in O(n) messages on complete graphs in synchronous networks. As we have verified in our private communications with Shay Kutten (Professor, Technion), the same message bound can be shown to hold in the simultaneous wake-up model as well under the restriction that the number of rounds is bounded by a function of n.

6. This enumeration is used only for the description of the lower bound construction and is unbeknownst to the nodes.

7. We note that this is the main idea borrowed from the Afek–Gafni algorithm [1]—the number of messages sent by each “active” node increases exponentially in every phase. That effect is, however, counterbalanced by the exponentially decreasing number of “active” nodes.

8. In contrast, we note that \(\varOmega (m)\) is a lower bound for deterministic on graphs of diameter at least three, even if n is known [10].

Authors and Affiliations

1. University of Houston, Houston, TX, 77204, USA

   Soumyottam Chatterjee & Gopal Pandurangan

2. McMaster University, Hamilton, ON, Canada

   Peter Robinson

Corresponding author

Correspondence to Soumyottam Chatterjee.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this work was nominated for the best paper award at the 19th International Conference on Distributed Computing and Networking (ICDCN 2018).

Gopal Pandurangan was supported, in part, by NSF Grants CCF-1527867, CCF-1540512, IIS-1633720, and CCF-1717075 and by US-Israel BSF Grant 2016419.

Peter Robinson was supported, in part, by the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2018-06322.

Appendix

1.1 Proof for function minima in Lemma 1

Proof

We define the Lagrangian as

where \(\lambda \) is the Lagrange multiplier. We can find the critical points of the Lagrangian by solving the set of equations

and

Simplifying Eq. (8), we get

One possible (feasible) solution of Eqs. (9) and (10) is,

and

Let \(X^*\) be a vector of dimension n defined by \(X^* {\mathop {=}\limits ^{{\mathsf {def}}}}(\frac{C}{n}, \frac{C}{n}, \ldots , \frac{C}{n})\). Then we have already shown that \(X^*\) and \(\lambda ^*\) are a critical point for the Lagrange function \(\mathscr {L}\). We claim that \(X^*\) is also a local minima for f(x) under the constraint of Eq. (9).

We show that by constructing the Bordered Hessian matrix \(H^B\) of the Lagrange function. Let \(L^*_{ij} {\mathop {=}\limits ^{{\mathsf {def}}}}\frac{\partial }{\partial x_j} (\frac{\partial \mathscr {L}}{\partial x_i})\big |_{X^*}\), where \(\mathscr {L}\) is the Lagrange function as defined in Eq. (7). Then

We note that \(L^*_{ii} = \frac{2\log {(\frac{C}{n})} - 1}{(\frac{C}{n})^3} - \lambda ^*\) for all \(1 \le i \le n\), and \(L^*_{ij} = 0\) for all (i, j) such that \(i \ne j\). Hence

We show that \(H^B\) is positive definite (which is a sufficient condition for \(X^*\) to be a local minima) by checking the signs of the leading principal minors. For any \(1 \le i \le n\), \(|H^B_i|\) is the determinant of a square matrix of dimension \(i+1\), and is given by

Hence

\(\square \)

1.2 Detailed proof of Lemma 10

Proof

Consider any \(u \in V\) such that \(u \ne v^{\text {max}}\).

• Case 1 (\(v^{\text {max}}\)anduare connected via an edge): Since \(v^{\text {max}}\) has the highest ID in G, the if-clause of Line 15 of Algorithm 2 is never satisfied for \(v^{\text {max}}\). Therefore \(v^{\text {max}}\) becomes inactive only if it has already sent probe-messages to all its neighbors (or \(v^{\text {max}}\) never becomes inactive). In particular, u always receives a probe-message from \(v^{\text {max}}\) containing \(ID_{v^{\text {max}}}\). Since \(ID_{v^{\text {max}}} > ID_u\), u becomes a non-candidate at that point (if u was still a candidate until that point) and therefore does not become a leader.

• Case 2 (\(v^{\text {max}}\)andudo not have an edge between them): By Observation 1, there is some \(x \in V\) such that both \(v^{\text {max}}\) and u have edges going to x. And we have already established that \(v^{\text {max}}\) will always send a probe-message to x at some point of time or another.

  • Case 2(a) (udoes not send a probe-message to x): This implies that u became inactive before it could send a probe-message to x. But then u could have become inactive only if the if-clause of Line 15 of Algorithm 2 got satisfied at some point. Then u became a non-candidate too at the same time and therefore would not become a leader.

  • Case 2(b) (usends a probe-message toxbefore \(v^{\text {max}}\)does): Suppose u sends a probe-message to x at round i and \(v^{\text {max}}\) sends a probe-message to x at round \(i'\), where \(1 \le i < i' \le \log {n}\). If x had seen an ID higher than \(ID_u\) up until round i, then x immediately informs u and u becomes a non-candidate.

    So suppose not. Then, after round i, x sets its local variables \(L_x\) and \(N_x\) to \(ID_u\) and u respectively. Let \(j > i\) be the smallest integer such that x receives a probe-message from a neighbor \(u'\) at round j, where \(ID_{u'} > ID_u\). Note that \(v^{\text {max}}\) will always send a probe-message to x, therefore such a \(u'\) exists. Then, after round j, x sets its local variables \(L_x\) and \(N_x\) to \(ID_{u'}\) and \(u'\) respectively, and informs u of this change (please see Line 17 of Algorithm 2). u becomes a non-candidate at that point of time.

  • Case 2(c) (uand\(v^{\text {max}}\)each sends a probe-message toxat the same time): Since \(ID_{v^{\text {max}}}\) is the highest ID in the network, \(L_x\) is assigned the value \(ID_{v^{\text {max}}}\) at this point, and x tells u about \(L_x = ID_{v^{\text {max}}} > ID_u\), causing u to become a non-candidate.

  • Case 2(d) (usends a probe-message to xafter \(v^{\text {max}}\)does): Suppose \(v^{\text {max}}\) sends a probe-message to x at round i and u sends a probe-message to x at round \(i'\), where \(1 \le i < i' \le \log {n}\). Then x sets its local variables \(L_x\) and \(N_x\) to \(ID_{v^{\text {max}}}\) and \(v^{\text {max}}\), respectively, after round i. So when u comes probing at round \(i' > i\), x tells u about \(L_x = ID_{v^{\text {max}}} > ID_u\), causing u to become a non-candidate. \(\square \)

1.3 Detailed proof of Lemma 11

Proof

Consider a node v that is active at the end of round i. This implies that the if-clause of Line 15 of Algorithm 2 has not so far been satisfied for v, which in turn implies that \(ID_v > ID_{w_{v, j}}\) for \(1 \le j \le 2^i - 1\), therefore none of

is active after round i. Thus for every active node at the end of round i, there are at least \(2^i - 1\) inactive nodes. We call this set of inactive nodes, together with v itself, the “kingdom” of v after round i, i.e.,

If we can show that these kingdoms are disjoint for two different active nodes, then we are done.

Proof by contradiction. Suppose not. Suppose there are two active nodes u and v such that

(after some round i, \(1 \le i \le \log {n}\)). Let x be such that \(x \in {\textit{KINGDOM}}_i(u) \cap {\textit{KINGDOM}}_i(v)\). Since an active node obviously cannot belong to the kingdom of another active node, this x equals neither u nor v, and therefore

that is, both u and v have sent their respective probe-messages to x. Without loss of generality, let \(ID_v > ID_u\).

• Case 1 (usends a probe-message to xbeforevdoes): Suppose u sends a probe-message to x at round j and v sends a probe-message to x at round \(j'\), where \(1 \le j < j' \le i\). If x had seen an ID higher than \(ID_u\) up until round j, then x immediately informs u and u becomes inactive. Contradiction.

  So suppose not. Then, after round j, x sets its local variables \(L_x\) and \(N_x\) to \(ID_u\) and u respectively. Let \(k > j\) be the smallest integer such that x receives a probe-message from a neighbor \(u'\) at round k, where \(ID_{u'} > ID_u\). Note that v sends a probe-message to x at round \(j'\), where \(j < j' \le i\), and \(ID_v > ID_u\). Therefore such a \(u'\) exists. Then, after round k, x sets its local variables \(L_x\) and \(N_x\) to \(ID_{u'}\) and \(u'\) respectively, and informs u of this change (please see Line 17 of Algorithm 2). u becomes inactive at that point of time, i.e., after round k, where \(k \le j' \le i\). Contradiction.

• Case 2 (uandveach sends a probe-message to xat the same time): Suppose that u and v each sends a probe-message to x at the same round j, where \(1 \le j \le i\). Since \(ID_v > ID_u\), x has at least one neighbor \(u'\) such that \(ID_{u'} > ID_u\). Therefore x would not set \(L_x\) to \(ID_u\) (or \(N_x\) to u), and x would inform u about that after round j, causing u to then become inactive. Contradiction.

• Case 3 (usends a probe-message toxaftervdoes): Suppose v sends a probe-message to x at round j and u sends a probe-message to x at round \(j'\), where \(1 \le j < j' \le i\). Then x sets its local variables \(L_x\) and \(N_x\) to \(ID_v\) and v, respectively, after round j. So when u comes probing at round \(j' > j\), x tells u about \(L_x \ge ID_v > ID_u\), causing u to become inactive. Contradiction. \(\square \)

1.4 Detailed proof of Lemma 13

Proof

We consider the two cases separately—when n is even and when n is odd—in order to make the presentation simpler.

• Case 1: \(n = 2k\)for some integer\(k \ge 2\).

Proof by contradiction. Suppose that there are three or more nodes that have had \(\lceil \frac{n}{2}\rceil = k\) or more edges removed each (either by themselves or by their neighbors). Let u, v, and w be three such nodes. Since an edge is removed only if one of the incident nodes has a higher ID than the other, all of (u, v), (v, w), and (w, u) cannot have been removed. Thus by a simple counting argument (by the “principle of inclusion–exclusion”), the total number of edges removed is at least \((3k - 3) + 1 = 3k - 2 > 2k - 1 = n - 1\), which contradicts Observation 4.

• Case 2: \(n = 2k + 1\)for some integer\(k \ge 1\).

Proof by contradiction Suppose that there are three or more nodes that have had \(\lceil \frac{n}{2}\rceil = k + 1\) or more edges removed each (either by themselves or by their neighbors). Let u, v, and w be three such nodes. Since an edge is removed only if one of the incident nodes has a higher ID than the other, all of (u, v), (v, w), and (w, u) cannot have been removed. Thus by a simple counting argument (by the “principle of inclusion–exclusion”), the total number of edges removed is at least \((3(k + 1) - 3) + 1 = 3k + 1 > 2k = n - 1\), which contradicts Observation 4. \(\square \)

1.5 Detailed proof of Lemma 14

Proof

Clearly \(G'\) is not of diameter one since the node with the smallest ID in V always drops at least one edge. Now let us consider any pair of nodes u and v, say. We show that the distance between u and v cannot be greater than 2.

If \((u, v) \in E'\), then we are already done. So suppose \((u, v) \notin E'\). Next we show that for any \(u, v \in V\), either u and v are directly connected in \(G'\) or \(\exists w \in V\) such that \((u, w) \in E'\) and \((w, v) \in E'\).

We consider the two cases—when n is even and when n is odd—separately, in order to make the presentation simpler.

• Case 1: \(n = 2k\)for some integer\(k \ge 2\).

  Since no node exists in \(G'\) which has had \(\lceil \frac{n}{2}\rceil = k\) or more edges removed, every node in \(G'\) has degree at least \((n - 1) - (k - 1) = k\). Thus for any \(u, v \in V\), if \((u, v) \notin E'\), then there are at least \(k + k - (n - 2) = 2\) nodes in \(V {\setminus } \left\{ u, v\right\} \) that are common neighbors to both u and v.

• Case 2: \(n = 2k + 1\)for some integer\(k \ge 1\).

  Since no node exists in \(G'\) which has had \(\lceil \frac{n}{2}\rceil = k + 1\) or more edges removed, that implies that every node in \(G'\) has degree at least \((n - 1) - k = k\). Thus for any \(u, v \in V\), if \((u, v) \notin E'\), then there is at least \(k + k - (n - 2) = 1\) node in \(V {\setminus } \left\{ u, v\right\} \), which is a common neighbor to both u and v. \(\square \)

Reprints and permissions