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.

Distal tephrochronology in volcanic regions: Challenges and insights from Kamchatkan lake sediments

Kamchatka is one of the world’s most active volcanic regions and has hosted many explosive eruptions during the Holocene. These eruptions had the potential to disperse tephra over wide areas, forming time-synchronous markers wherever those tephras are found. Recent research in Kamchatka has begun to focus on the geochemical analysis of individual glass shards in order to characterise tephra layers. We have applied this approach to the study of visible tephras from three lakes – one in central and two in northern Kamchatka – with the aim of identifying key tephras and potential issues in the application of distal (>100 km from an active volcano) tephra in volcanically complex regions. In total, 23 tephras from 22 tephra beds have been geochemically analysed, representing products from at least four volcanic systems in Kamchatka. We demonstrate that distal lake sediments in the region can yield reliable tephrostratigraphies, capturing tephra from eruptions that have the greatest potential to disperse volcanic ash beyond the region. We draw attention to issues relating to correlating and distinguishing key marker horizons from the highly active Shiveluch Volcano, namely the need to ensure inter-lab comparability of geochemical data and good chronological control of the proximal and distal tephras. Importantly, we have also extended the known distribution of two key tephra isochrons from the Ksudach volcano. Our work contributes valuable glass geochemical on data several key marker beds that will facilitate future tephra and palaeoenvironmental research within and beyond Kamchatka.

Progress towards improving chronologies for marine sediment records.

The North Atlantic has played a key role in abrupt climate changes due to the sensitivity of the Atlantic Meridional Overturning Circulation (AMOC) to the location and strength of deep water formation. It is crucial for modelling future climate change to understand the role of the AMOC in the rapid warming and gradual cooling cycles known as Dansgaard-Oescher (DO) events which are recorded in the Greenland ice cores. However, palaeoceanographic research into DO events has been hampered by the uncertainty in timing due largely to the lack of a precise chronological time frame for marine records. While tephrochronology provides links to the Greenland ice core records at a few points, radiocarbon remains the primary dating method for most marine cores. Due to variations in the atmospheric and oceanic 14C concentration, radiocarbon ages must be calibrated to provide calendric ages. The IntCal Working Group provides a global estimate of ocean 14C ages for calibration of marine radiocarbon dates, but the variability of the surface marine reservoir age in the North Atlantic particularly during Heinrich or DO events, makes calibration uncertain. In addition, the current Marine09 radiocarbon calibration beyond around 15 ka BP is largely based on 'tuning' to the Hulu Cave isotope record, so that the timing of events may not be entirely synchronous with the Greenland ice cores. The use of event-stratigraphy and independent chronological markers such as tephra provide the scope to improve marine radiocarbon reservoir age estimates particularly in the North Atlantic where a number of tephra horizons have been identified in both marine sediments and the Greenland ice cores. Quantification of timescale uncertainties is critical but statistical techniques which can take into account the differential dating between events can improve the precision. Such techniques should make it possible to develop specific marine calibration curves for selected regions.

The significance of interconnector counter-trading in a security constrained electricity market

Throughout the European Union there is an increasing amount of wind generation being dispatched-down due to the binding of power system operating constraints from high levels of wind generation. This paper examines the impact a system non-synchronous penetration limit has on the dispatch-down of wind and quantifies the significance of interconnector counter-trading to the priority dispatching of wind power. A fully coupled economic dispatch and security constrained unit commitment model of the Single Electricity Market of the Republic of Ireland and Northern Ireland and the British Electricity Trading and Transmission Arrangement was used in this study. The key finding was interconnector counter-trading reduces the impact the system non-synchronous penetration limit has on the dispatch-down of wind. The capability to counter-trade on the interconnectors and an increase in system non-synchronous penetration limit from 50% to 55% reduces the dispatch-down of wind by 311 GW h and decreases total electricity payments to the consumer by €1.72/MW h. In terms of the European Union electricity market integration, the results show the importance of developing individual electricity markets that allow system operators to counter-trade on interconnectors to ensure the priority dispatch of the increasing levels of wind generation.

Exploiting dynamic timing margins in microprocessors for frequency-over-scaling with instruction-based clock adjustment

Static timing analysis provides the basis for setting the clock period of a microprocessor core, based on its worst-case critical path. However, depending on the design, this critical path is not always excited and therefore dynamic timing margins exist that can theoretically be exploited for the benefit of better speed or lower power consumption (through voltage scaling). This paper introduces predictive instruction-based dynamic clock adjustment as a technique to trim dynamic timing margins in pipelined microprocessors. To this end, we exploit the different timing requirements for individual instructions during the dynamically varying program execution flow without the need for complex circuit-level measures to detect and correct timing violations. We provide a design flow to extract the dynamic timing information for the design using post-layout dynamic timing analysis and we integrate the results into a custom cycle-accurate simulator. This simulator allows annotation of individual instructions with their impact on timing (in each pipeline stage) and rapidly derives the overall code execution time for complex benchmarks. The design methodology is illustrated at the microarchitecture level, demonstrating the performance and power gains possible on a 6-stage OpenRISC in-order general purpose processor core in a 28nm CMOS technology. We show that employing instruction-dependent dynamic clock adjustment leads on average to an increase in operating speed by 38% or to a reduction in power consumption by 24%, compared to traditional synchronous clocking, which at all times has to respect the worst-case timing identified through static timing analysis.

Wide-Area Phase-Angle Measurements for Islanding Detection—An Adaptive Nonlinear Approach

The integration of an ever growing proportion of large scale distributed renewable generation has increased the probability of maloperation of the traditional RoCoF and vector shift relays. With reduced inertia due to non-synchronous penetration in a power grid, system wide disturbances have forced the utility industry to design advanced protection schemes to prevent system degradation and avoid cascading outages leading to widespread blackouts. This paper explores a novel adaptive nonlinear approach applied to islanding detection, based on wide area phase angle measurements. This is challenging, since the voltage phase angles from different locations exhibit not only strong nonlinear but also time-varying characteristics. The adaptive nonlinear technique, called moving window kernel principal component analysis is proposed to model the time-varying and nonlinear trends in the voltage phase angle data. The effectiveness of the technique is exemplified using both DigSilent simulated cases and real test cases recorded from the Great Britain and Ireland power systems by the OpenPMU project.

A Microgrid Testbed for Interdisciplinary Research on Cyber-Secure Industrial Control in Power Systems

This paper describes a smart grid test bed comprising embedded generation, phasor measurement units (PMUs), and supporting ICT components and infrastructure. The test bed enables the development of a use case focused on a synchronous islanding scenario, where the embedded generation becomes islanded from the mains supply. Due to the provisioned control components, control strategy, and best-practice ICT support infrastructure, the islanded portion of the grid is able to continue to operate in a secure and dependable manner.