---
_id: '9951'
abstract:
- lang: eng
  text: "There has recently been a surge of interest in the computational and complexity
    properties of the population model, which assumes n anonymous, computationally-bounded
    nodes, interacting at random, with the goal of jointly computing global predicates.
    Significant work has gone towards investigating majority or consensus dynamics
    in this model: that is, assuming that every node is initially in one of two states
    X or Y, determine which state had higher initial count.\r\n\r\nIn this paper,
    we consider a natural generalization of majority/consensus, which we call comparison
    : in its simplest formulation, we are given two baseline states, X and Y, present
    in any initial configuration in fixed, but possibly small counts. One of these
    states has higher count than the other: we will assume |X_0| > C |Y_0| for some
    constant C > 1. The challenge is to design a protocol by which nodes can quickly
    and reliably decide on which of the baseline states X_0 and Y_0 has higher initial
    count. We begin by analyzing a simple and general dynamics solving the above comparison
    problem, which uses O( log n ) states per node, and converges in O(log n) (parallel)
    time, with high probability, to a state where the whole population votes on opinions
    X or Y at rates proportional to the initial concentrations of |X_0| vs. |Y_0|.
    We then describe how this procedure can be bootstrapped to solve comparison, i.e.
    have every node in the population reach the \"correct'' decision, with probability
    1 - o(1), at the cost of O (log log n) additional states. Further, we prove that
    this dynamics is self-stabilizing, in the sense that it converges to the correct
    decision from arbitrary initial states, and leak-robust, in the sense that it
    can withstand spurious faulty reactions, which are known to occur in practical
    implementations of population protocols. Our analysis is based on a new martingale
    concentration result relating the discrete-time evolution of a population protocol
    to its expected (steady-state) analysis, which should be a useful tool when analyzing
    opinion dynamics and epidemic dissemination in the population model."
acknowledgement: We would like to thank Rati Gelashvili for very useful discussions,
  and the PODC anonymous reviewers for their careful reading of our paper, and for
  their useful remarks. This work is partially supported by the Polish National Science
  Center (NCN) grant UMO2017/25/B/ST6/02010.
article_processing_charge: No
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Martin
  full_name: Töpfer, Martin
  id: 4B865388-F248-11E8-B48F-1D18A9856A87
  last_name: Töpfer
- first_name: Przemysław
  full_name: Uznański, Przemysław
  last_name: Uznański
citation:
  ama: 'Alistarh D-A, Töpfer M, Uznański P. Comparison dynamics in population protocols.
    In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>.
    Association for Computing Machinery; 2021:55-65. doi:<a href="https://doi.org/10.1145/3465084.3467915">10.1145/3465084.3467915</a>'
  apa: 'Alistarh, D.-A., Töpfer, M., &#38; Uznański, P. (2021). Comparison dynamics
    in population protocols. In <i>Proceedings of the 2021 ACM Symposium on Principles
    of Distributed Computing</i> (pp. 55–65). Virtual, Italy: Association for Computing
    Machinery. <a href="https://doi.org/10.1145/3465084.3467915">https://doi.org/10.1145/3465084.3467915</a>'
  chicago: Alistarh, Dan-Adrian, Martin Töpfer, and Przemysław Uznański. “Comparison
    Dynamics in Population Protocols.” In <i>Proceedings of the 2021 ACM Symposium
    on Principles of Distributed Computing</i>, 55–65. Association for Computing Machinery,
    2021. <a href="https://doi.org/10.1145/3465084.3467915">https://doi.org/10.1145/3465084.3467915</a>.
  ieee: D.-A. Alistarh, M. Töpfer, and P. Uznański, “Comparison dynamics in population
    protocols,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed
    Computing</i>, Virtual, Italy, 2021, pp. 55–65.
  ista: 'Alistarh D-A, Töpfer M, Uznański P. 2021. Comparison dynamics in population
    protocols. Proceedings of the 2021 ACM Symposium on Principles of Distributed
    Computing. PODC: Symposium on Principles of Distributed Computing, 55–65.'
  mla: Alistarh, Dan-Adrian, et al. “Comparison Dynamics in Population Protocols.”
    <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>,
    Association for Computing Machinery, 2021, pp. 55–65, doi:<a href="https://doi.org/10.1145/3465084.3467915">10.1145/3465084.3467915</a>.
  short: D.-A. Alistarh, M. Töpfer, P. Uznański, in:, Proceedings of the 2021 ACM
    Symposium on Principles of Distributed Computing, Association for Computing Machinery,
    2021, pp. 55–65.
conference:
  end_date: 2021-07-30
  location: Virtual, Italy
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2021-07-26
date_created: 2021-08-22T22:01:20Z
date_published: 2021-07-21T00:00:00Z
date_updated: 2023-08-11T10:56:04Z
day: '21'
department:
- _id: DaAl
doi: 10.1145/3465084.3467915
external_id:
  isi:
  - '000744439800005'
isi: 1
language:
- iso: eng
month: '07'
oa_version: None
page: 55-65
publication: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - '9781450385480'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Comparison dynamics in population protocols
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '6759'
abstract:
- lang: eng
  text: "We consider the graph class Grounded-L corresponding to graphs that admit
    an intersection representation by L-shaped curves, where additionally the topmost
    points of each curve are assumed to belong to a common horizontal line. We prove
    that Grounded-L graphs admit an equivalent characterisation in terms of vertex
    ordering with forbidden patterns. \r\nWe also compare this class to related intersection
    classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max
    point-tolerance graphs), or the outer-1-string graphs. We give constructions showing
    that these classes are all distinct and satisfy only trivial or previously known
    inclusions."
article_number: P3.17
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vít
  full_name: Jelínek, Vít
  last_name: Jelínek
- first_name: Martin
  full_name: Töpfer, Martin
  id: 4B865388-F248-11E8-B48F-1D18A9856A87
  last_name: Töpfer
citation:
  ama: Jelínek V, Töpfer M. On grounded L-graphs and their relatives. <i>Electronic
    Journal of Combinatorics</i>. 2019;26(3). doi:<a href="https://doi.org/10.37236/8096">10.37236/8096</a>
  apa: Jelínek, V., &#38; Töpfer, M. (2019). On grounded L-graphs and their relatives.
    <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics.
    <a href="https://doi.org/10.37236/8096">https://doi.org/10.37236/8096</a>
  chicago: Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.”
    <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics,
    2019. <a href="https://doi.org/10.37236/8096">https://doi.org/10.37236/8096</a>.
  ieee: V. Jelínek and M. Töpfer, “On grounded L-graphs and their relatives,” <i>Electronic
    Journal of Combinatorics</i>, vol. 26, no. 3. Electronic Journal of Combinatorics,
    2019.
  ista: Jelínek V, Töpfer M. 2019. On grounded L-graphs and their relatives. Electronic
    Journal of Combinatorics. 26(3), P3.17.
  mla: Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.”
    <i>Electronic Journal of Combinatorics</i>, vol. 26, no. 3, P3.17, Electronic
    Journal of Combinatorics, 2019, doi:<a href="https://doi.org/10.37236/8096">10.37236/8096</a>.
  short: V. Jelínek, M. Töpfer, Electronic Journal of Combinatorics 26 (2019).
date_created: 2019-08-04T21:59:20Z
date_published: 2019-07-19T00:00:00Z
date_updated: 2022-03-18T12:32:02Z
day: '19'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.37236/8096
ec_funded: 1
external_id:
  arxiv:
  - '1808.04148'
file:
- access_level: open_access
  checksum: 20fc366fc6683ef0b074a019b73a663a
  content_type: application/pdf
  creator: dernst
  date_created: 2019-08-05T06:46:55Z
  date_updated: 2020-07-14T12:47:39Z
  file_id: '6764'
  file_name: 2019_eJourCombinatorics_Jelinek.pdf
  file_size: 533697
  relation: main_file
file_date_updated: 2020-07-14T12:47:39Z
has_accepted_license: '1'
intvolume: '        26'
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: Electronic Journal of Combinatorics
publication_identifier:
  eissn:
  - '10778926'
publication_status: published
publisher: Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: On grounded L-graphs and their relatives
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2019'
...