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 paper 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. The "obvious" lower bounds of O(m) messages (m is the number of edges in the network) and O(D) time (D is the network diameter) are non-trivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even O(n) (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 limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that D and n were not known).

We establish these fundamental lower bounds in this paper 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 (such algorithms should 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 anyuse of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time algorithm is known. A slight adaptation of our lower bound technique gives rise to an O(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 trade-off messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

Sublinear Bounds for Randomized Leader Election

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) takes only O(n-vlog3/2n) messages to elect a unique leader (with high probability). This algorithm is then extended to solve leader election on any connected non-bipartiten-node graph G in O(t(G)) time and O(t(G)n-vlog3/2n) messages, where t(G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficientdeterministic leader election algorithms. Finally, an almost-tight lower bound is presented for randomized leader election, showing that O(n-v) messages are needed for any O(1) time leader election algorithm which succeeds with high probability. It is also shown that O(n 1/3) messages are needed by any leader election algorithm that succeeds with high probability, regardless of the number of the rounds. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

Sublinear bounds for randomized leader election

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) uses only O(√ √nlog^3/2n) messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(. n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O(τ(. G)) time and O(τ(G)n√log^3/2n) messages, where τ(. G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω(n) messages are needed for any leader election algorithm that succeeds with probability at least 1/. e+. ε, for any small constant ε. >. 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

Holding parties responsible at election time: Multi-level, multi-party government and electoral accountability

This paper highlights the crucial role played by party-specific responsibility attributions in performance-based voting. Three models of electoral accountability, which make distinct assumptions regarding citizens' ability to attribute responsibility to distinct governing parties, are tested in the challenging Northern Ireland context - an exemplar case of multi-level multi-party government in which expectations of performance based voting are low. The paper demonstrates the operation of party-attribution based electoral accountability, using data from the 2011 Northern Ireland Assembly Election Study. However, the findings are asymmetric: accountability operates in the Protestant/unionist bloc but not in the Catholic/nationalist bloc. This asymmetry may be explained by the absence of clear ethno-national ideological distinctions between the unionist parties (hence providing political space for performance based accountability to operate) but the continued relevance in the nationalist bloc of ethno-national difference (which limits the scope for performance politics). The implications of the findings for our understanding of the role of party-specific responsibility attribution in performance based models of voting, and for our evaluation of the quality of democracy in post-conflict consociational polities, are discussed. 

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.

The Northern Ireland Assembly Election 2011

Following the first full term of regional government in the province since 1972, the Northern Ireland Assembly election held on 5 May 2011 saw the continuation of several trends. Foremost, the Democratic Unionist Party and Sinn Féin bolstered further their positions as leaders of their respective communities, with the Social Democratic and Labour Party and Ulster Unionist Party losing yet more ground. Building on their decision to enter power-sharing government together in 2007, the two largest parties framed themselves as the progressive choice for voters. As this was the first Assembly election since St Andrews (2006), much of the campaign dialogue centred on the prospect of a Sinn Féin First Minister, a concern highlighted by both unionist parties. The campaign also focused on ‘normal’ socio-economic political issues and possible institutional reform. The absence of inter-party conflict led to the campaign being perceived as the most mundane in living memory, with fears of a record low turnout realised.

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.

Campaign speech of W.D. Mayfield [for re-election as State Superintendent of Education]

This speech was given by Mr. Mayfield while running for re-election to the office of State Superintendent of Education. He gives evidence and reasons that he should be re-elected. He also talks about his future plans for if he does get re-elected.

The 2015 Portuguese Legislative Election: Widening the Coalitional Space and Bringing the Extreme Left in

This article provides an overview of the Portuguese legislative election held on 4 October 2015 by exploring the economic and political context in which the election took place, the opinion polls, party positions and campaign issues, the results and, finally, the process that led to the formation of the first Socialist minority government supported by far-left parties. Due to this outcome, despite the relative majority of the votes obtained by the incumbent centre-right coalition, we argue that this election result cannot be interpreted as a victory of austerity, but rather as the first step towards contract parliamentarism in Portugal.