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.

Increasingly ‘Irrational’ Party Systems: Evidence that There Are Increasingly More Than Two at the District level

Recent work has noted an increase in the number of parties at the national level in both proportional and majoritarian electoral systems. While the conventional wisdom maintains that the incentives provided by the electoral system will prevent the number of parties at the district level from exceeding two in majoritarian systems, the evidence presented here demonstrates otherwise. I argue that this has occurred because the number of cleavages articulated by parties has increased as several third parties have begun articulating cleavages that are not well represented by the two larger parties.

The British conservative party and Europe:The choosing of John Major

This article provides an empirical analysis of voting behaviour in the second ballot of the 1990 Conservative leadership contest that resulted in John Major becoming party leader and prime minister. Seven hypotheses of voting behaviour are generated from the extant literature relating voting to socio-economic variables (occupational and educational background), political variables (parliamentary experience, career status, age and electoral marginality) and ideological variables (drawn from survey data on MPs' positions on economic, European and moral issues). These hypotheses are tested using data on voting intentions gathered from published lists of MPs' declarations, interviews with each of the leadership campaign teams, and correspondence with MPs. Bivariate relationships are presented, followed by logistic regression analysis to isolate the unique impact that each variable had on voting. This shows that educational background, parliamentary experience and (especially) attitudes to Europe were the key factors determining voting. The importance of Europe in the contest is particularly instructive: the severe problems for Major's leadership which were caused by the issue can be attributed to, and understood in the context of, the 1990 contest in which he became leader.

The Ulster Covenant and the Pulse of Protestant Ulster

The signing of the Ulster Covenant on 28 September 1912 by almost 450,000 men and women was a powerful act of defiance on the part of Unionists in the context of what they perceived as the threat to their way of life represented by the Liberal Government's policy of Irish Home Rule. This article attempts to look beyond the well-studied leadership figures of Carson and Craig in order to fashion insights into the way Ulster Protestant society was mobilised around the Covenant and opposition to Home Rule. It draws attention to hitherto over-shadowed personalities who can be said to have exerted crucial local influence. It also contends that although pan-Protestant denominational unity provided the basis for the success of the Covenant, the Presbyterian community was particularly cohesive and purposeful in the campaign. The article further argues that the risk-taking defiance that came more easily to the Presbyterians, on account of a troubled history, largely evaporated in the new political circumstances of Northern Ireland when it became a separate devolved political entity within the UK from 1921.

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.

From 'trailing wives' to the emergence of a 'trailing husbands' phenomenon: Retirement migration to rural areas

Migration and gender studies have focused on economically active heterogeneous couples and traditionally highlight a dominant male role in migration decision-making. The female partner is commonly portrayed as a 'trailing wife' or 'trailing mother' with the move found to have a negative effect on her employment prospects. Much less is known about if or how the balance of power shifts between husbands and wives when employment or career-motivated moves are removed from the decision-making process. This is analysed with reference to retirement migration to rural areas of the UK and involved interviews with both partners present. For this cohort of retired couples, and in common with the literature, migration during economically active life course stages demonstrates strong 'trailing wife' and 'trailing mother' tendencies. The male's decision to retire signalled the commencement of a retirement life course stage for the couple. However, in contrast to the earlier male dominated decision-making, retirement migration saw the emergence of a 'trailing husband' phenomenon. Wives appear to adapt most successfully to the new rural environment while many husbands found it difficult to adjust (at least initially) to the multiple life changes: moving from largely urban areas to a rural setting alongside exiting the workforce. The findings suggest that the role of leader/ follower changed during the course of these couples' lives together and in relation to their reasons for moving.