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.

Secure Communication in Cellular Networks: The Benefits of Millimeter Wave Mobile Broadband

This paper proposes millimeter wave (mmWave) mobile broadband for achieving secure communication in downlink cellular network. Analog beamforming with phase shifters is adopted for the mmWave transmission. The secrecy throughput is analyzed based on two different transmission modes, namely delay-tolerant transmission and delay-limited transmission. The impact of large antenna arrays at the mmWave frequencies on the secrecy throughput is examined. Numerical results corroborate our analysis and show that mmWave systems can enable significant secrecy improvement. Moreover, it is indicated that with large antenna arrays, multi-gigabit per second secure link at the mmWave frequencies can be reached in the delay-tolerant transmission mode and the adverse effect of secrecy outage vanishes in the delay-limited transmission mode.

Population Mobility Dynamics Estimated from Mobile Telephony Data

In the last decade, mobile phones and mobile devices using mobile cellular telecommunication network connections have become ubiquitous. In several developed countries, the penetration of such devices has surpassed 100 percent. They facilitate communication and access to large quantities of data without the requirement of a fixed location or connection. Assuming mobile phones usually are in close proximity with the user, their cellular activities and locations are indicative of the user's activities and movements. As such, those cellular devices may be considered as a large scale distributed human activity sensing platform. This paper uses mobile operator telephony data to visualize the regional flows of people across the Republic of Ireland. In addition, the use of modified Markov chains for the ranking of significant regions of interest to mobile subscribers is investigated. Methodology is then presented which demonstrates how the ranking of significant regions of interest may be used to estimate national population, results of which are found to have strong correlation with census data.