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.

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.

‘A true feeling of authentic portuguese golf'? The discursive construction of the Algarve region in portuguese golf websites

In an increasingly competitive global marketplace, the need for golf destinations to differentiate themselves from competitors has become more critical than ever. This paper raises questions about the promotional strategies employed by the golf sector in the Algarve, focusing on internet communication strategies, since this medium has become the biggest driving force towards the commoditisation of all aspects of the tourism experience. By offering a complementary perspective to the field of (critical) tourism studies, and drawing on a qualitative, multi-modal discourse analysis, this work-in-progress looks at the particular ways that representations and images presented on the Algarve golf websites constitute and frame identities (of people and places) and socio-spatial relationships. This paper analyses a corpus of 45 texts collected from official websites of the 40 Algarve golf courses and from five entities which promote the Algarve as a golf destination, along with the golf images that are displayed alongside them. Findings point to salient discursive and visual representations of a global setting enjoyed by the global elite. Whereas the courses‟ positioning in relation to their regional competitors draws on similar discursive strategies which reflect those used in tourism advertising discourses in general – e.g. reiteration of explicit comparisons, superlatives and hyperbolic statements -, representations of local emplacedness are not salient; in some cases local place seems to have been almost intentionally suppressed.

The influence of authentic leadership on employees analyzed through self-determination theory

Dissertação de Mestrado, Gestão de Recursos Humanos, Escola Superior de Gestão, Hotelaria e Turismo, Faculdade de Ciências Humanas e Sociais, Universidade do Algarve, 2015

Privatization and government preference in a public Stackelberg leader duopoly

We analyse the relationship between the privatization of a public firm and government preferences for tax revenue in a Stackelberg duopoly with the public firm as the leader. We assume that the government payoff is given by a weighted sum of tax revenue and the sum of consumer and producer surplus. We get that if the government puts a sufficiently larger weight on tax revenue than on the sum of both surpluses, it will not privatize the public firm. In contrast, if the government puts a moderately larger weight on tax revenue than on the sum of both surpluses, it will privatize the public firm.

Environmental taxes in a public Stackelberg leader duopoly

We study whether privatization of a public firm improves (or deteriorates) the environment in a mixed Stackelberg duopoly with the public firm as the leader. We assume that each firm can prevent pollution by undertaking abatement measures. We get that, since in the mixed market the industry output is higher than in the private market, the abatement levels are also higher in the mixed market, and, thus, environmental tax rate in the mixed duopoly is higher than that in the privatized duopoly. Furthermore, the environment is more damaged in the mixed than in the private market. The overall effect on the social welfare is that it will becomes higher in the private than in the mixed market.

The impact of talent management practices on employee retention: The moderator effect of leader-member exchange and role modeling

Organizations are undergoing serious difficulties to retain talent. Authors argue that Talent Management (TM) practices create beneficial outcomes for individuals and organizations. However, there is no research on the leaders’ role in the functioning of these practices. This study examines how LMX and role modeling influence the impact that TM practices have on employees’ trust in their organizations and retention. The analysis of two questionnaires (Nt1=175; Nt2=107) indicated that TM only reduced turnover intentions, via an increase in trust in the organization, when role modeling was high and not when it was low. Therefore, we can say that leaders are crucial in the TM context, and in sustaining a competitive advantage for organizations.

Ethical leadership and unethical pro-organizational behavior: A moderated mediation model of affective commitment and authenticity at work

Recently, unethical conduct in the workplace has been a focus of literature and media. Unethical pro-organizational behavior (UPB) refers to unethical conduct that employees engage in to benefit the organization. Given the complexity of UPB, there is an increasing need to understand how and under what conditions this attitude originates within organizations. Based on a sample of 167 employees and seven organizations, results support the moderated mediation model. An ethical leader increases employees’ organizational affective commitment which increases the likelihood to engage in UPB. However, the indirect relationship diminishes when employees feel authentic at work.

Psychological safety, authentic leadership and social networks : A psycho-structural approach to the study of groups

Tese de Doutoramento em Psicologia na área de especialização de Psicologia das Organizações apresentada ao ISPA - Instituto Universitário

A qualitative approach to define the prototype of a Portuguese expatriate leader in Angola

This qualitative research analyzes the individual life experiences of Portuguese expatriate leaders who left their home country to work at organizations in Angola, a place that offers better job opportunities. Through interviews with those professionals and their followers, a prototype of a Portuguese expatriate leader in Angola has been developed. Even though Angola is a former Portuguese colony, it was at war for many years and so the economic situation and culture of the country are distant from what Portuguese workers are used too, which requires them to adapt and be open-minded to change.