We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Consensus Potpourri: Approximate Majority With Catalytic Inputs

Formal Metadata

Title
Consensus Potpourri: Approximate Majority With Catalytic Inputs
Title of Series
Number of Parts
30
Author
License
CC Attribution 4.0 International:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Third-state dynamics (Angluin et al. 2008; Perron et al. 2009) is a well-known process for quickly and robustly computing approximate majority through interactions between randomly-chosen pairs of agents. In this paper, we consider this process in a new model with persistent-state catalytic inputs, as well as in the presence of transient leak faults. Based on models considered in recent protocols for populations with persistent-state agents (Dudek et al. 2017; Alistarh et al. 2017; Alistarh et al. 2020), we formalize a Catalytic Input (CI) model comprised of n input agents and m worker agents. For m=Θ(n), we show that computing the PARITY of the input population with high probability requires at least Ω(n2) total interactions, demonstrating a strong separation between the CI and standard population models. On the other hand, we show that the third-state dynamics can be naturally adapted to this new model to solve approximate majority in O(nlogn) total steps with high probability when the input margin is Ω(√nlogn) , which preserves the time and space efficiency of the process in the original model. Moreover we show the robustness of third-state dynamics protocols to the transient leak faults considered by (Alistarh et al. 2017; Alistarh et al 2020). In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each time step with probability β≤O(√nlognn) . The resilience of these dynamics to adversarial leaks exhibits a subtle connection to previous results involving Byzantine agents.