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

Formale Metadaten

Titel
Consensus Potpourri: Approximate Majority With Catalytic Inputs
Serientitel
Anzahl der Teile
30
Autor
Lizenz
CC-Namensnennung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.