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.

Women’s Perceptions and Experiences of Fetal Macrosomia

Objective
to explore women's perceptions and experiences of pregnancy and childbirth following birth of a macrosomic infant (birth weight ≥4000 g).

Methods
a qualitative design utilising interviews conducted 13–19 weeks post partum in women's homes. The study was conducted in one Health and Social Care Trust in Northern Ireland between January and September 2010. Participants were identified from a larger cohort of women recruited to a prospective study exploring the impact of physical activity and nutrition on macrosomia. Eleven women who delivered macrosomic infants participated in this phase of the study.

Findings
four overarching themes emerged: preparation for delivery; physical and emotional impact of macrosomia; professional relations and perceptions of macrosomia. Findings highlighted the importance of communication with health professionals in relation to both prediction of macrosomia and decision making about childbirth, and offers further understanding into the physical and emotional impact of having a macrosomic infant on women. Furthermore, there was evidence that beliefs and perceptions relating to macrosomia may influence birth experiences and uptake of health promotion messages.

Key conclusions and implications for practice
this study provides important insight into women's experiences of macrosomia throughout the perinatal period and how they were influenced by previous birth experiences, professional relations and personal perceptions and beliefs about macrosomia. Pregnant women at risk of having a macrosomic infant may require extra support throughout the antenatal period continuing into the postnatal period. Support needs to be tailored to the woman's information needs, with time allocated to explore previous birth experiences, beliefs about macrosomia and options for childbirth.

DEX: Self-Healing Expanders

We present a fully-distributed self-healing algorithm DEX, that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders - whose expansion properties hold deterministically - that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only probabilistic guarantees on the network expansion which rapidly degrade in a dynamic setting, in particular, the expansion properties can degrade even more rapidly under adversarial insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only O(log n) rounds and O(log n) messages are needed with high probability (n is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table (DHT) on top of DEX, with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have guaranteed properties (constant bounded degree and expansion) despite dynamic changes.

Development of a continuing professional development website to raise awareness of preconception counselling and pre-pregnancy care for Women with Diabetes

Aims: Pre-pregnancy care reduces the risk of adverse pregnancy outcomes in women with diabetes, yet the majority of women receive suboptimal care due to poor preconception counselling rates and a lack of awareness about the importance of specialised pre-pregnancy care. The primary aim was to develop a continuing professional development (CPD) resource for healthcare professionals (HCPs) who work with women with diabetes to facilitate preconception counselling with this group.

Methods: The website was developed under the direction of a multidisciplinary team, adhering to NICE guidelines. The tone, key messages and format are informed by the “Women with Diabetes” preconception counselling website, www.womenwithdiabetes.net, an existing resource which is effective in helping women to be better prepared for pregnancy.Results: This e-learning resource will give HCPs the necessary knowledge and tools to prepare women with diabetes to plan for pregnancy. The website features women with diabetes sharing their views and experiences, alongside an evidence-based commentary and key messages from research papers and clinical guidelines. It comprises two modules: “Planning for Pregnancy”, focusing on contraception, risks and planning; and “Diabetes and Pregnancy”, focusing on support during pregnancy with an overview of each trimester of pregnancy.

Conclusion: This website will be a useful CPD resource for all HCPs working with women with diabetes, providing a certificate on completion. This resource will empower HCPs to engage in preconception counselling with women with diabetes by providing the HCP with a greater understanding of the specific needs of women with diabetes both preconception and during pregnancy.

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.

Penser la guerre au XXIe siècle

Ce numéro était déjà sous presse quand, le 13 novembre 2015, Paris était une nouvelle fois la cible d’attentats terroristes d’une ampleur sans précédent, faisant plus d’une centaine de morts. Le Président François Hollande parla cette fois, de manière répétée, d’‘un acte de guerre’. Des voix solidaires se sont élevées des quatre coins de la planète, soulignant bien que, à travers la France, ce sont bien les valeurs qu’elle représente et qu’elle partage avec nombre de pays que les assassins de Daech visaient. Parmi tous les messages de solidarité, il nous semble important de souligner celui d’Hassan Rohani, le Président iranien, et celui d’Abdelaziz Bouteflika, le Président algérien: immédiatement, le premier ‘condamn[ait] avec vigueur ces crimes contre l'humanité et présent[ait] [s]es condoléance au peuple français endeuillé et au gouvernement’; le second dénonçait sans réserve ‘cette horreur planifiée [qui] constitue un véritable crime contre l'humanité’. Quant à Anouar Kbibech, le nouveau président du Conseil français du culte musulman, il ‘condamn[ait] avec la plus grande vigueur ces attaques inqualifiables’ et ‘appel[ait] à se regrouper autour de ces valeurs qui font la France’. Plus que jamais, il faut éviter les amalgames pour ne pas faire le jeu des minorités extrémistes.

This is Abuse… Or is it? Domestic abuse perpetrators’ responses to anti-domestic violence publicity

Social marketing has become a key component of policy initiatives aimed at reducing the incidence of domestic abuse. However, its efficacy remains debated, with most measures of effectiveness being somewhat crude. More subtle effects of social marketing, such as the boomerang effect whereby the message engenders the opposite effect to that intended, have been detected, suggesting a need for modes of analysis sensitive to the multiple ways in which viewers react to social opprobrium. This article attempts to deliver just this. It begins with a short history and critique of the concept of social marketing. It then proceeds to explore the utility of the more complex notion that viewers often identify with the subject positions thrown open by social marketing on a quite temporary basis, before reconfiguring them. Using the responses of domestic abuse perpetrators exposed to the UK Government’s This is Abuse campaign film, the article shows how contradictory identifications with both anti-violence messages and victim-blaming discourses are negotiated by those young men prone to perpetrating domestic abuse. The article concludes by exploring how effectiveness might be better conceptualised and assessed with regard to the impact of anti-violence social marketing that speaks to domestic abuse perpetrators.

Reconstructing ethical conduct within financial firms

This chapter explores whether ethical cultures can be created within a financial market context. Ongoing regulatory and legal actions, and press coverage of these, suggest that a definition of ethical problems in terms of ‘rogue traders’ and ‘bad apples’ would be inadequate, since entire business areas have been resorting to collusive illegal behaviour. The concept of ‘bad barrels’ seems to capture the situation rather better: the culture of firms fails to discourage transgression and indeed supports it. Unpacking the links between regulatory objectives and the cultural settings of firms and their employees, this chapter questions the chances of success of measures such as enhanced controls on individuals and restructured reward mechanisms. Financial firms typically have very flat, nodal structures, within which traders conceptualise themselves as an elite, in contrast to back office staff and also in contrast to managers. Traders’ functions and their occupational mobility mean that their linkages and attachments may be much stronger with others outside ‘their’ firm than their firm and those within it. Performance, camaraderie and their linkages are important in all work situations, yet all the more so for traders in financial markets. Thus, whether regulators and senior management combine to send a clear and consistent message to traders – or whether the logic of the financial marketplace leads some firms to continue send conflicting or ambivalent messages to them – misconduct is likely to continue to be a tough nut to crack.

Understanding informal kinship care: a critical narrative review of theory and research

Many children are cared for on a full-time basis by relatives or adult friends, rather than their biological parents, and often in response to family crises. These kinship care arrangements have received increasing attention from the social science academy and social care professions. However, more information is needed on informal kinship care that is undertaken without official ratification by welfare agencies and often unsupported by the state. This article presents a comprehensive, narrative review of international, research literature on informal, kinship care to address this gap. Using systematic search and review protocols, it synthesises findings regarding: (i) the way that informal kinship care is defined and conceptualised; (ii) the needs of the carers and children; and (iii) ways of supporting this type of care. A number of prominent themes are highlighted including the lack of definitional clarity; the various adversities experienced by the families; and the requirement to understand the interface between formal and informal supports. Key messages are finally identified to inform the development of family friendly policies, interventions, and future research.

The Aran jumper: Crafting a Transatlantic Heritage

The garment we now recognise as the Aran jumper emerged as an international symbol of Ireland from the twin twentieth century transatlantic flows of migration and tourism. Its power as a heritage object derives from: 1) the myth commonly associated with the object, in which the corpse of a drowned fisherman is identified and claimed by his family due to the stitch patterns of his jumper (Pádraig Ó Síochain 1962; Annette Lynch and Mitchell Strauss 2014); 2) the meanings attached to those stitch patterns, which have been read, for example, as genealogical records, representations of the natural landscape and references to Christian and pre-Christian ‘Celtic’ religion (Heinz Kiewe 1967; Catherine Nash 1996); and 3) booming popular interest in textile heritage on both sides of the Atlantic, fed by the reframing of domestic crafts such as knitting as privileged leisure pursuits (Rachel Maines 2009; Jo Turney 2009). The myth of the drowned fisherman plays into transatlantic migration narratives of loss and reclamation, promising a shared heritage that needs only to be decoded. The idea of the garment’s surface acting as text (or map) situates it within a preliterate idyll of romantic primitivism, while obscuring the circumstances of its manufacture. The contemporary resurgence in home textile production as recreation, mediated through transnational online networks, creates new markets for heritage textile products while attracting critical attention to the processes through which such objects, and mythologies, are produced. The Aran jumper’s associations with kinship, domesticity and national character make it a powerful tool in the promotion of ancestral (or genealogical) tourism, through marketing efforts such as The Gathering 2013. Nash’s (2010; 2014) work demonstrates the potential for such touristic encounters to disrupt and enrich public conceptions of heritage, belonging and relatedness. While the Aran jumper has been used to commodify a simplistic sense of mutuality between Ireland and north America, it carries complex transatlantic messages in both directions.

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.

DEX: self-healing expanders

Living long and ageing well: is epigenomics the missing link between nature and nurture?

Human longevity is a complex trait and increasingly we understand that both genes and lifestyle interact in the longevity phenotype. Non-genetic factors, including diet, physical activity, health habits, and psychosocial factors contribute approximately 50 % of the variability in human lifespan with another 25 % explained by genetic differences. Family clusters of nonagenarian and centenarian siblings, who show both exceptional age-span and health-span, are likely to have inherited facilitatory gene groups, but also have nine decades of life experiences and behaviours which have interacted with their genetic profiles. Identification of their shared genes is just one small step in the link from genes to their physical and psychological profiles. Behavioural genomics is beginning to demonstrate links to biological mechanisms through regulation of gene expression, which directs the proteome and influences the personal phenotype. Epigenetics has been considered the missing link between nature and nurture. Although there is much that remains to be discovered, this article will discuss some of genetic and environmental factors which appear important in good quality longevity and link known epigenetic mechanisms to themes identified by nonagenarians themselves related to their longevity. Here we suggest that exceptional 90-year old siblings have adopted a range of behaviours and life-styles which have contributed to their ageing-well-phenotype and which link with important public health messages.

Symposium - Organisational transformation in policing: Leadership and change in extreme contexts

Nearly 4000 people died in Northern Ireland’s long running conflict, 314 of them police officers (Brewer and Magee 1991, Brewer 1996, Hennessey 1999, Guelke and Milton-Edwards 2000). The republican and loyalist ceasefires of 1994 were the first significant signal that NI society was moving beyond the ‘troubles’ and towards a normalised political environment. The Belfast (Good Friday) Agreement of 1998 cemented that movement (Hennessey 1999). Policing was a key and seemingly unresolvable element of the conflict, seen as unrepresentative and partisan. Its reform or ‘recasting’ in a new dispensation was an integral part of the conflict transformation endeavour(Ellison 2010). As one of the most controversial elements of the conflicted past, it had remained outside the Agreement and was subject to a specific commission of interest (1999), generally known as the Patten Commission. The Commission’s far reaching proposals included a change of name, badge and uniform, the introduction of 50/50 recruitment (50% Roman Catholic and 50% other), a new focus on human rights, a new district command and headquarter structure, a review of ‘Special Branch’ and covert techniques, a concern for ‘policing with the community’ and a significant voluntary severance process to make room for new recruits, unconnected with the past history of the organisation(Murphy 2013).

This paper reflects upon the first data collection phase of a long term processual study of organisational change within the Royal Ulster Constabulary / Police Service of Northern Ireland. This phase (1996-2002) covers early organisational change initiation (including the pre-change period) and implementation including the instigation of symbolic changes (name, badge, and crest) and structural changes (new HQ structure and District Command structure). It utilises internal documentation including messages from the organisations leaders, interviews with forty key informants (identified through a combination of snow-balling from referrals by initial contacts, and key interviews with significant individuals), as well as external documentation and commentary on public perceptions of the change. Using a processual lens (Langley, Smallman et al. 2013) it seeks to understand this initial change phase and its relative success in a highly politicised environment.

By engaging key individuals internally and externally, setting up a dedicated change team, adopting a non normative, non urgent, calming approach to dissent, communicating in orthodox and unorthodox ways with members, acknowledging the huge emotional strain of letting go of the organisation’s name and all it embodied, and re-emphasising the role of officers as ‘police first’, rather than ‘RUC first’, the organisations leadership remained in control of a volatile and unhappy organisational body and succeeded in moving it on through this initial phase, even while much of the political establishment lambasted them externally. Three years into this change process the organisation had a new name, a new crest, new structures, procedures and was deeply engaged in embedding the joint principles of human rights and community policing within its re-woven fabric. While significant problems remained, the new Police Service of Northern Ireland had successfully begun a long journey to full community acceptance in a post conflict context.

This case illustrates the significant challenges of leading change under political pressure, with external oversight and no space for failure(Hannah, Uhl-Bien et al. 2009). It empirically reflects the reality of change implementation as messy, disruptive and unpredictable and highlights the significance of political skill and contextual understanding to success in the early stages(Buchanan and Boddy 1992). The implications of this for change theory and the practice of change implementation are explored (Eisenhardt and Graebner 2007) and some conclusions drawn about what such an extreme case tells us about change generally and change implementation under pressure.

‘Twenty-six things at once’: Pragmatic perspectives on Frank O’Hara and Norman Bluhm’s Poem-Paintings

Created over a couple of Sunday mornings in the Fall of 1960, the twenty-six collaborative Poem-Paintings of the artist Norman Bluhm and the poet Frank O'Hara represent what Bluhm later called a spontaneous 'conversation' between the painter and the poet. In this essay, Catherine Gander adopts a number of pragmatist positions to reconsider these overlooked works as essential examples of verbal-visual interaction that extend their 'conversation' to greet and involve us in a relationship that is at once interpersonal, integrated, and embodied. The works, Gander argues, constitute what John Dewey terms 'art as experience'; in their back and forth exchange of verbal and visual gesture, abstraction and denotation, the Poem-Paintings are the 'cumulative continuity' of 'the process of living', dramatising the shifting, spontaneous and multiple dimensions of interpersonal conversation, and in so doing, indicating a new path toward interconnective and equal exchange between word and image.