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.

Reparation or retribution: an investigation into regulatory compliance in planning

It is an axiom of good planning practice that procedure is informed by up-to-date research. Consequently, it is surprising to discover that there remains a dearth of specialised planning-enforcement literature relating to theory and implementation. In this paper an evaluation is given of the effectiveness of planning enforcement in Britain by reviewing existing legislative mechanisms and strategies employed by officials. Theoretical perspectives are drawn upon to suggest how the system might be improved through attention to the structural factors underpinning it.

Devolving Housing Policy and Practice in Northern Ireland 1998 - 2002

This paper reviews the effect of devolution on housing policy and practice in Northern Ireland. It outlines the history and context of devolution and housing policy in Northern Ireland, including the legacy and persistence of intense social conflict. Current devolution arrangements are reviewed, including the implications of enforced coalition for policy governance. The paper focuses on three dimensions of housing and housing-related policy development and implementation: social housing, especially the distinctive history and changing organisation of social housing provision; policies affecting the housing market, including the changing regime for spatial planning; and, regeneration and tenant participation. The paper argues that housing policy has tended to converge with policies in England, rather than moving towards a distinctively local agenda. Local political agendas remain dominated by disagreements over constitutional status, thus policy formulation is determined more by officials than by elected politicians.

Crystal structure and ab initio calculations of a cyano-carbamimidic acid ethyl ester

The structure of one tautomer (amine form) of cyano-carbamimidic acid ethyl ester or (amino-ethoxy-methylidene)aminoformonitrile (CAS: 13947-84-7) was determined by single crystal X-ray diffraction. Ab initio quantum chemical calculations at the B3LYP, MP2 and G3 levels were performed to investigate the stability and the formation of the different tautomers and conformers. The calculations indicate that the amine form is the more stable tautomer, showing a high degree of election conjugation. The most stable amine conformer located by the calculations corresponds to the crystallized structure. On the contrary, in the less stable imine form, the conjugation is separated by a N2-C2 single bond. (C) 2007 Elsevier B.V. All rights reserved.

Order without law? An anatomy of Hamas security: The Executive Force (Tanfithya)

In the struggle to assert and consolidate its power, the Hamas movement of the Palestinian territories has devised several strategies for control. In recognition that control of security remains a key goal for any power-seeker, following its election victory in January 2006, Hamas entered into a fierce and ultimately successful conflict with Fatah for control of the Palestinian Authority Ministry of Interior and Palestinian Security Forces (PSF) in the Gaza Strip. One way in which Hamas was able to achieve this objective was through the creation of its own internal ‘police’ force called the Tanfithya (Executive Force or EF). This article details an anatomy of the EF and the implications of this force in terms of Hamas' confrontation with opponents and its attempts at governance. It also examines the extent to which the EF can be considered to be a model of Islamic policing and its impact on secular rivals in the Gaza Strip.

Northern Ireland: The Politics of Constraint

The article surveys the interrupted experience of devolution in Northern Ireland since 1999 and draws a number of comparisons between the first devolved Assembly and Executive and their successors elected in 2007. It underlines the significance of the changed political, electoral and paramilitary context in the period leading up to the 2007 Assembly election which, together with a number of procedural changes effected by the 2006 St Andrews Agreement, enabled the restoration of power-sharing devolution to occur. Against the background of its legislative and policy record and the wider altered state of Northern Ireland, it concludes that the contrived consociational model of governance can work, up to a point, but perhaps as much because of the politics of constraint than consociationalism's much vaunted promise to reflect and engender the politics of accommodation.

Agitating for a design and regeneration agenda in a postconflict city: the case of Belfast

Introduction

Belfast has been a focus of academic attention for the last forty years with most interest centred on various aspects of ‘the Troubles’. Where there has been interest in the built environment, it has largely been about how the ‘security situation’ impacted directly on architecture and on the design and layout of social housing. This paper seeks to go beyond this to explore how the political- administrative culture of ‘the Troubles’ interacted with ‘normal’ market forces to shape the central area of the city, and to consider the responses of a recently formed activist group, known as the Forum for Alternative Belfast (hereafter referred to as the Forum). The paper is written by three of the directors of the Forum.1 Moreover, the empirical research presented here was undertaken by the Forum as part of a campaign to address issues relating to the design, layout and quality of Belfast’s built environment. In the longstanding tradition of participant observation working within an action-research paradigm, the participants have attempted to offer an account that is evidentially and purposefully selfcritical and reflective. It is of course recognised that while this approach offers many positive attributes, such as phenomenological access through immersion in the project, it also has the potential to bring compromise on research detachment and objectivity.2 To address the latter, the authors have attempted
to avoid polemical argument, and to support claims with primary or secondary research evidence. The authors also acknowledge that action-research has a chequered history; however, they would argue
that their approach is faithful to a concept that sees ‘research’ defined as understanding and ‘action’ defined as seeking change. The Forum’s very purpose is to seek change, but to do this requires evidence, collaboration and demonstration. And in this sense, it is a learning process for all participants, including the research activists, government officials, community organisations and students. The authors also recognise the complexity of factors that affect urban management and change, particularly in a city such as Belfast, which has had to cope with political violence for over thirty years. And they appreciate that in the context of conflict, governance is skewed to cope with political realities. Hamdi reminds us, however, that in practice there is an ‘important dialectic between top-down planning, with its formal and designed laws and structures, and bottom-up selforganizing collectivism—those “quantum and emergent systems” which Jane Jacobs argued long ago give cities their life and order.’3

Irish social thought and the relief of poverty, 1847-1880

This paper investigates the way in which the ‘problem of poverty’ in Ireland was encountered, constructed and debated by members of the Irish intellectual and political elite in the decades between the Great Famine and the outbreak of the land war in the late 1870s. This period witnessed acute social upheavals in Ireland, from the catastrophic nadir of the Famine, through the much-vaunted economic recovery of the 1850s–1860s, to the near-famine panic of the late 1870s (itself prefigured by a lesser agricultural crisis in 1859–63). The paper focuses on how a particular elite group – the ‘Dublin School’ of political economists and their circle, and most prominently William Neilson Hancock and John Kells Ingram – sought to define and investigate the changing ‘problem’, shape public attitudes towards the legitimacy of welfare interventions and lobby state officials in the making of poor law policy in this period. It suggests that the crisis of 1859–63 played a disproportionate role in the reevaluation of Irish poor relief and in promoting a campaign for an ‘anglicisation’ of poor law measures and practice in Ireland.