On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of Ω(m) messages, where m is the number of edges in the network, and Ω(D) time, where D is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even Ω(n), where n is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that D and n were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an Ω(m) message lower bound for randomized broadcast algorithms. 

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

Fast Byzantine Leader Election in Dynamic Networks

We study the fundamental Byzantine leader election problem in dynamic networks where the topology can change from round to round and nodes can also experience heavy {\em churn} (i.e., nodes can join and leave the network continuously over time). We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power and can deviate arbitrarily from the protocol. The churn is controlled by an adversary that has complete knowledge and control over which nodes join and leave and at what times and also may rewire the topology in every round and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is an $O(\log^3 n)$ round algorithm that achieves Byzantine leader election under the presence of up to $O({n}^{1/2 - \epsilon})$ Byzantine nodes (for a small constant $\epsilon > 0$) and a churn of up to \\$O(\sqrt{n}/\poly\log(n))$ nodes per round (where $n$ is the stable network size).The algorithm elects a leader with probability at least $1-n^{-\Omega(1)}$ and guarantees that it is an honest node with probability at least $1-n^{-\Omega(1)}$; assuming the algorithm succeeds, the leader's identity will be known to a $1-o(1)$ fraction of the honest nodes. Our algorithm is fully-distributed, lightweight, and is simple to implement. It is also scalable, as it runs in polylogarithmic (in $n$) time and requires nodes to send and receive messages of only polylogarithmic size per round.To the best of our knowledge, our algorithm is the first scalable solution for Byzantine leader election in a dynamic network with a high rate of churn; our protocol can also be used to solve Byzantine agreement in a straightforward way.We also show how to implement an (almost-everywhere) public coin with constant bias in a dynamic network with Byzantine nodes and provide a mechanism for enabling honest nodes to store information reliably in the network, which might be of independent interest.

Plus Ça Change: The 2014 Local Elections in Northern Ireland

The local government elections of 22 May 2014 in Northern Ireland were the first to be held under revised district boundaries, with 11 'super councils' replacing the 26-council model used since 1973. Despite the structural reform, little changed in terms of political party support. Although they suffered some losses, the Democratic Unionist Party and Sinn Féin remained firmly entrenched as the two dominant players at local government level in Northern Ireland. The Ulster Unionist Party enjoyed only a marginal increase in its vote share, while the Social Democratic and Labour Party recorded one of the worst electoral performances in its history. Elsewhere, the Traditional Unionist Voice enjoyed a 'breakthrough' election and the Alliance Party defied widely held predictions that it would suffer at the polls as a result of its role in the Union flag crisis. The campaign was overshadowed by both the concurrent European Parliament contest and several crises of power-sharing at Stormont. As a result, distinctly local government issues received scant and fleeting attention. The contest saw the lowest local election turnout in Northern Ireland's history, continuing a general trend of increasing voter apathy in the province.

Effective collision strengths for election impact excitation of Cl III

Effective collision strengths for electron-impact excitation of the phosphorus-like ion Cl III are presented for all fine-structure transitions among the levels arising from the lowest 23 LS states. The collisional cross sections are computed in the multichannel close-coupling R-matrix approximation, where sophisticated configuration-interaction wave functions are used to represent the target states. The 23 LS states are formed from the basis configurations 3s²3p³, 3s3p⁴, 3s²3p²3d, and 3s²3p²4s, and correspond to 49 fine-structure levels, leading to a total possible 1176 fine-structure transitions. The effective collision strengths, obtained by averaging the electron collision strengths over a Maxwellian distribution of electron velocities, are tabulated in this paper for all 1176 transitions and for electron temperatures in the ranges T(K)=7500-25,000 and log T(K)=4.4-5.4. The former range encompasses the temperatures of particular importance for application to gaseous nebulae, while the latter range is more applicable to the study of solar and laboratory-type plasmas. © 2001 Academic Press.