2 Search Results for "Lazarsfeld, John"

Document
DOI: 10.4230/LIPIcs.DISC.2025.27
On the h-Majority Dynamics with Many Opinions

Authors: Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We present the first upper bound on the convergence time to consensus of the well-known h-majority dynamics with k opinions, in the synchronous setting, for h and k that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by x nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is ω(√x) and the initial plurality opinion is supported by at least x = ω(log n) nodes, then the process converges to plurality consensus in O(log n) rounds whenever h = ω(n log n / x). A main corollary is the following: if k = o(n / log n) and the process starts from an almost-balanced configuration with an initial bias of magnitude ω(√{n/k}) towards the initial plurality opinion, then any function h = ω(k log n) suffices to guarantee convergence to consensus in O(log n) rounds, with high probability. Our upper bound shows that the lower bound of Ω(k / h²) rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than Ω̃(k / h). Moreover, the bias we require is asymptotically smaller than the Ω(√{nlog n}) bias that guarantees plurality consensus in the 3-majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in ω(√x) for any value of k ≥ 2.
Cite as

Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale. On the h-Majority Dynamics with Many Opinions. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{damore_et_al:LIPIcs.DISC.2025.27,
  author =	{d'Amore, Francesco and D'Archivio, Niccol\`{o} and Giakkoupis, George and Natale, Emanuele},
  title =	{{On the h-Majority Dynamics with Many Opinions}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{27:1--27:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.27},
  URN =		{urn:nbn:de:0030-drops-248448},
  doi =		{10.4230/LIPIcs.DISC.2025.27},
  annote =	{Keywords: Distributed Algorithms, Randomized Algorithms, Markov Chains, Consensus Problem, Opinion dynamics, Plurality Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.19
Approximate Majority with Catalytic Inputs

Authors: Talley Amir, James Aspnes, and John Lazarsfeld

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Population protocols [Dana Angluin et al., 2006] are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents [Bartlomiej Dudek and Adrian Kosowski, 2018; Alistarh et al., 2017; Dan Alistarh et al., 2020], we assume a population with n catalytic input agents and m worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For m = Θ(n), we show that computing the parity of the input population with high probability requires at least Ω(n²) total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics [Angluin et al., 2008; Perron et al., 2009] for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in O(n log n) total steps with high probability when the input margin is Ω(√{n log n}). We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by [Alistarh et al., 2017; Dan 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 step with probability β ≤ O(√{n log n}/n). The resilience of these dynamics to leaks exhibits similarities to previous work involving Byzantine agents, and we define and prove a notion of equivalence between the two.
Cite as

Talley Amir, James Aspnes, and John Lazarsfeld. Approximate Majority with Catalytic Inputs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.OPODIS.2020.19,
  author =	{Amir, Talley and Aspnes, James and Lazarsfeld, John},
  title =	{{Approximate Majority with Catalytic Inputs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.19},
  URN =		{urn:nbn:de:0030-drops-135040},
  doi =		{10.4230/LIPIcs.OPODIS.2020.19},
  annote =	{Keywords: population protocols, approximate majority, catalysts, leaks, lower bound}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021

  • Refine by Author
  • 1 Amir, Talley
  • 1 Aspnes, James
  • 1 D'Archivio, Niccolò
  • 1 Giakkoupis, George
  • 1 Lazarsfeld, John
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Applied computing → Systems biology
  • 1 Computing methodologies → Distributed algorithms
  • 1 Mathematics of computing → Markov processes
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Networks → Network protocols
  • Show More...

  • Refine by Keyword
  • 1 Consensus Problem
  • 1 Distributed Algorithms
  • 1 Markov Chains
  • 1 Opinion dynamics
  • 1 Plurality Consensus
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact