More Like this

1. Accountable Secret Leader Election

   https://doi.org/10.4230/LIPIcs.AFT.2024.1  

   Christ, Miranda; Choi, Kevin; McKelvie, Walter; Bonneau, Joseph; Malkin, Tal (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Böhme, Rainer; Kiffer, Lucianna (Ed.)

   We consider the problem of secret leader election with accountability. Secret leader election protocols counter adaptive adversaries by keeping the identities of elected leaders secret until they choose to reveal themselves, but in existing protocols this means it is impossible to determine who was elected leader if they fail to act. This opens the door to undetectable withholding attacks, where leaders fail to act in order to slow the protocol or bias future elections in their favor. We formally define accountability (in weak and strong variants) for secret leader election protocols. We present three paradigms for adding accountability, using delay-based cryptography, enforced key revelation, or threshold committees, all of which ensure that after some time delay the result of the election becomes public. The paradigm can be chosen to balance trust assumptions, protocol efficiency, and the length of the delay before leaders are revealed. Along the way, we introduce several new cryptographic tools including re-randomizable timed commitments and timed VRFs. 

   more » « less
2. Distributed leader following of an active leader for linear heterogeneous multi-agent systems

   https://doi.org/10.1016/j.sysconle.2020.104621  

   Chung, Yi-Fan; Kia, Solmaz S. (March 2020, Systems & Control Letters)

   null (Ed.)
3. Churn-tolerant Leader Election Protocols

   Jiangran Wang, Indranil Gupta (July 2023, Proceedings 43rd IEEE International Conference on Distributed Computing Systems)

   Classical leader election protocols typically assume complete and correct knowledge of underlying membership lists at all participating nodes. Yet many edge and IoT settings are dynamic, with nodes joining, leaving, and failing continuously—a phenomenon called churn. This implies that in any membership protocol, a given node’s membership list may have entries that are missing (e.g., false positive detections, or newly joined nodes whose information has not spread yet) or stale (e.g., failed nodes that are undetected)—these would render classical election protocols incorrect. We present a family of four leader election protocols that are churn-tolerant (or c-tolerant). The key ideas are to: i) involve the minimum number of nodes necessary to achieve safety; ii) use optimism so that decisions are made faster when churn is low; iii) incorporate a preference for electing healthier nodes as leaders. We prove the correctness and safety of our c-tolerant protocols and show their message complexity is optimal. We present experimental results from both a trace- driven simulation as well as our implementation atop Raspberry Pi devices, including a comparison against Zookeeper. 

   more » « less
4. Singularly Optimal Randomized Leader Election

   https://doi.org/10.4230/LIPIcs.DISC.2020.22  

   Kutten, Shay; Moses Jr., William K.; Pandurangan, Gopal; Peleg, David (January 2020, 34th International Symposium on Distributed Computing (DISC 2020))

   null (Ed.)

   This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks. Our main result is a randomized distributed leader election algorithm for asynchronous complete networks that is essentially (up to a polylogarithmic factor) singularly optimal. Our algorithm uses O(n) messages with high probability and runs in O(log² n) time (with high probability) to elect a unique leader. The O(n) message complexity should be contrasted with the Ω(n log n) lower bounds for the deterministic message complexity of leader election algorithms (regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for synchronous networks. Hence, our result also separates the message complexities of randomized and deterministic leader election. More importantly, our (randomized) time complexity of O(log² n) for obtaining the optimal O(n) message complexity is significantly smaller than the long-standing Θ̃(n) time complexity obtained by Afek and Gafni and by Singh (SIAM J. Comput., 1997) for message optimal (deterministic) election in asynchronous networks. Afek and Gafni also conjectured that Θ̃(n) time would be optimal for message-optimal asynchronous algorithms. Our result shows that randomized algorithms are significantly faster. Turning to synchronous complete networks, Afek and Gafni showed an essentially singularly optimal deterministic algorithm with O(log n) time and O(n log n) messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to improve the message complexity, and showed a randomized algorithm with O(n) messages but still with O(log n) time (with failure probability O(1 / log^{Ω(1)}n)). Our second result shows that synchronous complete networks admit a tightly singularly optimal randomized algorithm, with O(1) time and O(n) messages (both bounds are optimal). Moreover, our algorithm’s time bound holds with certainty, and its message bound holds with high probability, i.e., 1-1/n^c for constant c. Our results demonstrate that leader election can be solved in a simultaneously message and time-efficient manner in asynchronous complete networks using randomization. It is open whether this is possible in asynchronous general networks. 

   more » « less
5. On the Transition From Initial Leader to Stepped Leader in Negative Cloud‐to‐Ground Lightning

   https://doi.org/10.1029/2019JD031765  

   Stolzenburg, Maribeth; Marshall, Thomas C.; Karunarathne, Sumedhe (February 2020, Journal of Geophysical Research: Atmospheres)

   Abstract High‐speed video and electric field change data are used to describe the first 5 ms of a negative cloud‐to‐ground flash. These observations reveal an evolution in character of the luminosity and electric field change pulses as two branches of the leader separately transition from initial leader to propagating as a negative stepped leader (SL). For the first time reported, there is evidence of weak luminosity coincident with the initiating event, a weak bipolar pulse 60 μs prior to the first initial breakdown (IB) pulse. During the IB stage, the initial leader advances intermittently at intervals of 100–280 μs, in separate light bursts that are bright for a few 20‐μs frames and are time coincident with IB pulses. In the intervals between IB pulses, the initial leader is dim or invisible during the earliest 1.8 ms. Within 2 ms, the leader propagation begins transitioning to an early SL phase, in which the leader tip advances at more regular intervals of 40–80 μs during relatively dim and brief steps which are coincident with SL pulses having short duration, small amplitude, and typically unipolar waveform. These data indicate that when the entire initial leader length behind the lower end begins to remain illuminated between bursts, the propagation mode changes from IB bursts to SL steps, and the IB stage ends. The results support a hypothesis that the early initial leader development occurs in the absence of a continuously hot channel, thus the initial leader propagation is physically unlike the self‐propagating SL advance. 

   more » « less