---
_id: '9933'
abstract:
- lang: eng
text: "In this paper, we study the power and limitations of component-stable algorithms
in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari,
Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space
MPC algorithms, which are, informally, defined as algorithms for which the outputs
reported by the nodes in different connected components are required to be independent.
This very natural notion was introduced to capture most (if not all) of the known
efficient MPC algorithms to date, and it was the first general class of MPC algorithms
for which one can show non-trivial conditional lower bounds. In this paper we
enhance the framework of component-stable algorithms and investigate its effect
on the complexity of randomized and deterministic low-space MPC. Our key contributions
include: 1) We revise and formalize the lifting approach of Ghaffari, Kuhn and
Uitto. This requires a very delicate amendment of the notion of component stability,
which allows us to fill in gaps in the earlier arguments. 2) We also extend the
framework to obtain conditional lower bounds for deterministic algorithms and
fine-grained lower bounds that depend on the maximum degree Δ. 3) We demonstrate
a collection of natural graph problems for which non-component-stable algorithms
break the conditional lower bound obtained for component-stable algorithms. This
implies that, for both deterministic and randomized algorithms, component-stable
algorithms are conditionally weaker than the non-component-stable ones.\r\n\r\nAltogether
our results imply that component-stability might limit the computational power
of the low-space MPC model, paving the way for improved upper bounds that escape
the conditional lower bound setting of Ghaffari, Kuhn, and Uitto."
acknowledgement: This work is partially supported by a Weizmann-UK Making Connections
Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty
Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083,
the Minerva foundation with funding from the Federal German Ministry for Education
and Research No. 713238, and the European Union’s Horizon 2020 programme under the
Marie Skłodowska-Curie grant agreement No 754411.
article_processing_charge: No
arxiv: 1
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
citation:
ama: 'Czumaj A, Davies P, Parter M. Component stability in low-space massively parallel
computation. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing. Association for Computing Machinery; 2021:481–491. doi:10.1145/3465084.3467903'
apa: 'Czumaj, A., Davies, P., & Parter, M. (2021). Component stability in low-space
massively parallel computation. In Proceedings of the 2021 ACM Symposium on
Principles of Distributed Computing (pp. 481–491). Virtual, Italy: Association
for Computing Machinery. https://doi.org/10.1145/3465084.3467903'
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Component Stability in
Low-Space Massively Parallel Computation.” In Proceedings of the 2021 ACM Symposium
on Principles of Distributed Computing, 481–491. Association for Computing
Machinery, 2021. https://doi.org/10.1145/3465084.3467903.
ieee: A. Czumaj, P. Davies, and M. Parter, “Component stability in low-space massively
parallel computation,” in Proceedings of the 2021 ACM Symposium on Principles
of Distributed Computing, Virtual, Italy, 2021, pp. 481–491.
ista: 'Czumaj A, Davies P, Parter M. 2021. Component stability in low-space massively
parallel computation. Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing. PODC: Principles of Distributed Computing, 481–491.'
mla: Czumaj, Artur, et al. “Component Stability in Low-Space Massively Parallel
Computation.” Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2021, pp. 481–491, doi:10.1145/3465084.3467903.
short: A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2021 ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery, 2021,
pp. 481–491.
conference:
end_date: 2021-07-30
location: Virtual, Italy
name: 'PODC: Principles of Distributed Computing'
start_date: 2021-07-26
date_created: 2021-08-17T18:11:16Z
date_published: 2021-07-21T00:00:00Z
date_updated: 2023-08-17T07:11:32Z
day: '21'
department:
- _id: DaAl
doi: 10.1145/3465084.3467903
ec_funded: 1
external_id:
arxiv:
- '2106.01880'
isi:
- '000744439800049'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2106.01880
month: '07'
oa: 1
oa_version: Submitted Version
page: 481–491
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
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'
status: public
title: Component stability in low-space massively parallel computation
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_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: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing.
Association for Computing Machinery; 2021:55-65. doi:10.1145/3465084.3467915'
apa: 'Alistarh, D.-A., Töpfer, M., & Uznański, P. (2021). Comparison dynamics
in population protocols. In Proceedings of the 2021 ACM Symposium on Principles
of Distributed Computing (pp. 55–65). Virtual, Italy: Association for Computing
Machinery. https://doi.org/10.1145/3465084.3467915'
chicago: Alistarh, Dan-Adrian, Martin Töpfer, and Przemysław Uznański. “Comparison
Dynamics in Population Protocols.” In Proceedings of the 2021 ACM Symposium
on Principles of Distributed Computing, 55–65. Association for Computing Machinery,
2021. https://doi.org/10.1145/3465084.3467915.
ieee: D.-A. Alistarh, M. Töpfer, and P. Uznański, “Comparison dynamics in population
protocols,” in Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing, 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.”
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing,
Association for Computing Machinery, 2021, pp. 55–65, doi:10.1145/3465084.3467915.
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'
...