---
_id: '12566'
abstract:
- lang: eng
text: "Approximate agreement is one of the few variants of consensus that can be
solved in a wait-free manner in asynchronous systems where processes communicate
by reading and writing to shared memory. In this work, we consider a natural generalisation
of approximate agreement on arbitrary undirected connected graphs. Each process
is given a node of the graph as input and, if non-faulty, must output a node such
that\r\n– all the outputs are within distance 1 of one another, and\r\n– each
output value lies on a shortest path between two input values.\r\nFrom prior work,
it is known that there is no wait-free algorithm among processes for this problem
on any cycle of length , by reduction from 2-set agreement (Castañeda et al.,
2018).\r\n\r\nIn this work, we investigate the solvability of this task on general
graphs. We give a new, direct proof of the impossibility of approximate agreement
on cycles of length , via a generalisation of Sperner's Lemma to convex polygons.
We also extend the reduction from 2-set agreement to a larger class of graphs,
showing that approximate agreement on these graphs is unsolvable. On the positive
side, we present a wait-free algorithm for a different class of graphs, which
properly contains the class of chordal graphs."
acknowledgement: This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No. 805223 ScaleML) and under the Marie Skłodowska-Curie grant
agreement No. 840605 and from the Natural Sciences and Engineering Research Council
of Canada grant RGPIN-2020-04178. Part of this work was done while Faith Ellen was
visiting IST Austria.
article_number: '113733'
article_processing_charge: Yes (via OA deal)
article_type: original
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: Faith
full_name: Ellen, Faith
last_name: Ellen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs.
Theoretical Computer Science. 2023;948(2). doi:10.1016/j.tcs.2023.113733
apa: Alistarh, D.-A., Ellen, F., & Rybicki, J. (2023). Wait-free approximate
agreement on graphs. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2023.113733
chicago: Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate
Agreement on Graphs.” Theoretical Computer Science. Elsevier, 2023. https://doi.org/10.1016/j.tcs.2023.113733.
ieee: D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement
on graphs,” Theoretical Computer Science, vol. 948, no. 2. Elsevier, 2023.
ista: Alistarh D-A, Ellen F, Rybicki J. 2023. Wait-free approximate agreement on
graphs. Theoretical Computer Science. 948(2), 113733.
mla: Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Theoretical
Computer Science, vol. 948, no. 2, 113733, Elsevier, 2023, doi:10.1016/j.tcs.2023.113733.
short: D.-A. Alistarh, F. Ellen, J. Rybicki, Theoretical Computer Science 948 (2023).
date_created: 2023-02-19T23:00:55Z
date_published: 2023-02-28T00:00:00Z
date_updated: 2023-08-01T13:17:20Z
day: '28'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1016/j.tcs.2023.113733
ec_funded: 1
external_id:
isi:
- '000934262700001'
file:
- access_level: open_access
checksum: b27c5290f2f1500c403494364ee39c9f
content_type: application/pdf
creator: dernst
date_created: 2023-02-20T07:30:20Z
date_updated: 2023-02-20T07:30:20Z
file_id: '12570'
file_name: 2023_TheoreticalCompScience_Alistarh.pdf
file_size: 602333
relation: main_file
success: 1
file_date_updated: 2023-02-20T07:30:20Z
has_accepted_license: '1'
intvolume: ' 948'
isi: 1
issue: '2'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Wait-free approximate agreement on graphs
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 948
year: '2023'
...
---
_id: '11184'
abstract:
- lang: eng
text: "Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node.\r\nIn this work, we consider the more general setting where
G is an arbitrary regular graph, and present a technique for simulating protocols
designed for fully-connected networks in any connected regular graph. Our main
result is a simulation that is efficient on many interesting graph families: roughly,
the simulation overhead is polylogarithmic in the number of nodes, and quadratic
in the conductance of the graph. As a sample application, we show that, in any
regular graph with conductance φ, both leader election and exact majority can
be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability,
using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast
and space-efficient population protocols for leader election and exact majority
on graphs with good expansion properties. We believe our results will prove generally
useful, as they allow efficient technology transfer between the well-mixed (clique)
case, and the under-explored spatial setting."
acknowledgement: "Dan Alistarh: This project has received funding from the European
Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has
received from the European Union’s Horizon 2020 research and\r\ninnovation programme
under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements
We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock
construction to non-regular graphs. We also thank anonymous reviewers for their
useful comments on earlier versions of this manuscript."
alternative_title:
- LIPIcs
article_number: '14'
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: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols.
In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles
of Distributed Systems. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.OPODIS.2021.14'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2022). Fast graphical
population protocols. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th
International Conference on Principles of Distributed Systems (Vol. 217).
Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14'
chicago: Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical
Population Protocols.” In 25th International Conference on Principles of Distributed
Systems, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol.
217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.OPODIS.2021.14.
ieee: D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population
protocols,” in 25th International Conference on Principles of Distributed Systems,
Strasbourg, France, 2022, vol. 217.
ista: Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols.
25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs,
vol. 217, 14.
mla: Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” 25th
International Conference on Principles of Distributed Systems, edited by Quentin
Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, doi:10.4230/LIPIcs.OPODIS.2021.14.
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A.
Milani (Eds.), 25th International Conference on Principles of Distributed Systems,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2021-12-15
location: Strasbourg, France
name: OPODIS
start_date: 2021-12-13
date_created: 2022-04-17T22:01:47Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2022-05-02T08:09:39Z
day: '01'
ddc:
- '510'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.OPODIS.2021.14
ec_funded: 1
editor:
- first_name: Quentin
full_name: Bramas, Quentin
last_name: Bramas
- first_name: Vincent
full_name: Gramoli, Vincent
last_name: Gramoli
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: 2c7c982174c6f98c4ca6e92539d15086
content_type: application/pdf
creator: dernst
date_created: 2022-05-02T08:06:33Z
date_updated: 2022-05-02T08:06:33Z
file_id: '11346'
file_name: 2022_LIPICs_Alistarh.pdf
file_size: 959406
relation: main_file
success: 1
file_date_updated: 2022-05-02T08:06:33Z
has_accepted_license: '1'
intvolume: ' 217'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 25th International Conference on Principles of Distributed Systems
publication_identifier:
isbn:
- '9783959772198'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast graphical population protocols
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 217
year: '2022'
...
---
_id: '12182'
abstract:
- lang: eng
text: 'Online algorithms make decisions based on past inputs, with the goal of being
competitive against an algorithm that sees also future inputs. In this work, we
introduce time-local online algorithms; these are online algorithms in which the
output at any given time is a function of only T latest inputs. Our main observation
is that time-local online algorithms are closely connected to local distributed
graph algorithms: distributed algorithms make decisions based on the local information
in the spatial dimension, while time-local online algorithms make decisions based
on the local information in the temporal dimension. We formalize this connection,
and show how we can directly use the tools developed to study distributed approximability
of graph optimization problems to prove upper and lower bounds on the competitive
ratio achieved with time-local online algorithms. Moreover, we show how to use
computational techniques to synthesize optimal time-local algorithms.'
acknowledgement: "This research has received funding from the German Research Foundation
(DFG), grant\r\n470029389 (FlexNets), 2021-2024, and the Marie Skłodowska-Curie
grant agreement No. 840605."
article_number: '52'
article_processing_charge: No
author:
- first_name: Maciej
full_name: Pacut, Maciej
last_name: Pacut
- first_name: Mahmoud
full_name: Parham, Mahmoud
last_name: Parham
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Aleksandr
full_name: Tereshchenko, Aleksandr
last_name: Tereshchenko
citation:
ama: 'Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. Brief announcement:
Temporal locality in online algorithms. In: 36th International Symposium on
Distributed Computing. Vol 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.DISC.2022.52'
apa: 'Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J., & Tereshchenko,
A. (2022). Brief announcement: Temporal locality in online algorithms. In 36th
International Symposium on Distributed Computing (Vol. 246). Augusta, GA,
United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2022.52'
chicago: 'Pacut, Maciej, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela,
and Aleksandr Tereshchenko. “Brief Announcement: Temporal Locality in Online Algorithms.”
In 36th International Symposium on Distributed Computing, Vol. 246. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.DISC.2022.52.'
ieee: 'M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, and A. Tereshchenko,
“Brief announcement: Temporal locality in online algorithms,” in 36th International
Symposium on Distributed Computing, Augusta, GA, United States, 2022, vol.
246.'
ista: 'Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. 2022.
Brief announcement: Temporal locality in online algorithms. 36th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing vol.
246, 52.'
mla: 'Pacut, Maciej, et al. “Brief Announcement: Temporal Locality in Online Algorithms.”
36th International Symposium on Distributed Computing, vol. 246, 52, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.DISC.2022.52.'
short: M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, A. Tereshchenko,
in:, 36th International Symposium on Distributed Computing, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2022-10-27
location: Augusta, GA, United States
name: 'DISC: Symposium on Distributed Computing'
start_date: 2022-10-25
date_created: 2023-01-13T11:06:28Z
date_published: 2022-10-17T00:00:00Z
date_updated: 2023-01-27T06:59:29Z
day: '17'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2022.52
ec_funded: 1
file:
- access_level: open_access
checksum: 11bbb56f68a00f2cf6bcce6cc7f5c5f9
content_type: application/pdf
creator: dernst
date_created: 2023-01-27T06:58:02Z
date_updated: 2023-01-27T06:58:02Z
file_id: '12409'
file_name: 2022_LIPICs_Pacut.pdf
file_size: 524804
relation: main_file
success: 1
file_date_updated: 2023-01-27T06:58:02Z
has_accepted_license: '1'
intvolume: ' 246'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 36th International Symposium on Distributed Computing
publication_identifier:
eisbn:
- '9783959772556'
eissn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Temporal locality in online algorithms'
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 246
year: '2022'
...
---
_id: '11844'
abstract:
- lang: eng
text: "In the stochastic population protocol model, we are given a connected graph
with n nodes, and in every time step, a scheduler samples an edge of the graph
uniformly at random and the nodes connected by this edge interact. A fundamental
task in this model is stable leader election, in which all nodes start in an identical
state and the aim is to reach a configuration in which (1) exactly one node is
elected as leader and (2) this node remains as the unique leader no matter what
sequence of interactions follows. On cliques, the complexity of this problem has
recently been settled: time-optimal protocols stabilize in Θ(n log n) expected
steps using Θ(log log n) states, whereas protocols that use O(1) states require
Θ(n2) expected steps.\r\n\r\nIn this work, we investigate the complexity of stable
leader election on general graphs. We provide the first non-trivial time lower
bounds for leader election on general graphs, showing that, when moving beyond
cliques, the complexity landscape of leader election becomes very diverse: the
time required to elect a leader can range from O(1) to Θ(n3) expected steps. On
the upper bound side, we first observe that there exists a protocol that is time-optimal
on many graph families, but uses polynomially-many states. In contrast, we give
a near-time-optimal protocol that uses only O(log2n) states that is at most a
factor log n slower. Finally, we show that the constant-state protocol of Beauquier
et al. [OPODIS 2013] is at most a factor n log n slower than the fast polynomial-state
protocol. Moreover, among constant-state protocols, this protocol has near-optimal
average case complexity on dense random graphs."
acknowledgement: We thank the anonymous reviewers for their helpful comments. We gratefully
acknowledge funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No 805223
ScaleML).
article_processing_charge: Yes (via OA deal)
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: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Sasha
full_name: Voitovych, Sasha
last_name: Voitovych
citation:
ama: 'Alistarh D-A, Rybicki J, Voitovych S. Near-optimal leader election in population
protocols on graphs. In: Proceedings of the Annual ACM Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2022:246-256.
doi:10.1145/3519270.3538435'
apa: 'Alistarh, D.-A., Rybicki, J., & Voitovych, S. (2022). Near-optimal leader
election in population protocols on graphs. In Proceedings of the Annual ACM
Symposium on Principles of Distributed Computing (pp. 246–256). Salerno, Italy:
Association for Computing Machinery. https://doi.org/10.1145/3519270.3538435'
chicago: Alistarh, Dan-Adrian, Joel Rybicki, and Sasha Voitovych. “Near-Optimal
Leader Election in Population Protocols on Graphs.” In Proceedings of the Annual
ACM Symposium on Principles of Distributed Computing, 246–56. Association
for Computing Machinery, 2022. https://doi.org/10.1145/3519270.3538435.
ieee: D.-A. Alistarh, J. Rybicki, and S. Voitovych, “Near-optimal leader election
in population protocols on graphs,” in Proceedings of the Annual ACM Symposium
on Principles of Distributed Computing, Salerno, Italy, 2022, pp. 246–256.
ista: 'Alistarh D-A, Rybicki J, Voitovych S. 2022. Near-optimal leader election
in population protocols on graphs. Proceedings of the Annual ACM Symposium on
Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
Computing, 246–256.'
mla: Alistarh, Dan-Adrian, et al. “Near-Optimal Leader Election in Population Protocols
on Graphs.” Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2022, pp. 246–56, doi:10.1145/3519270.3538435.
short: D.-A. Alistarh, J. Rybicki, S. Voitovych, in:, Proceedings of the Annual
ACM Symposium on Principles of Distributed Computing, Association for Computing
Machinery, 2022, pp. 246–256.
conference:
end_date: 2022-07-29
location: Salerno, Italy
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2022-07-25
date_created: 2022-08-14T22:01:46Z
date_published: 2022-07-21T00:00:00Z
date_updated: 2023-06-14T12:06:01Z
day: '21'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3519270.3538435
ec_funded: 1
external_id:
arxiv:
- '2205.12597'
file:
- access_level: open_access
checksum: 4c6b29172b8e355b4fbc364a2e0827b2
content_type: application/pdf
creator: cchlebak
date_created: 2022-08-16T08:05:15Z
date_updated: 2022-08-16T08:05:15Z
file_id: '11854'
file_name: 2022_PODC_Alistarh.pdf
file_size: 1593474
relation: main_file
success: 1
file_date_updated: 2022-08-16T08:05:15Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 246-256
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing
publication_identifier:
isbn:
- '9781450392624'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Near-optimal leader election in population protocols on graphs
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_id: '11707'
abstract:
- lang: eng
text: 'In this work we introduce the graph-theoretic notion of mendability: for
each locally checkable graph problem we can define its mending radius, which captures
the idea of how far one needs to modify a partial solution in order to “patch
a hole.” We explore how mendability is connected to the existence of efficient
algorithms, especially in distributed, parallel, and fault-tolerant settings.
It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds
in the LOCAL model of distributed computing. One of the surprises is that in paths
and cycles, a converse also holds in the following sense: if a problem Π can be
solved in O(log∗n), there is always a restriction Π′⊆Π that is still efficiently
solvable but that is also O(1)-mendable. We also explore the structure of the
landscape of mendability. For example, we show that in trees, the mending radius
of any locally checkable problem is O(1), Θ(logn), or Θ(n), while in general graphs
the structure is much more diverse.'
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 840605. This work was supported in part by the Academy of Finland, Grants 314888
and 333837. The authors would also like to thank David Harris, Neven Villani, and
the anonymous reviewers for their very helpful comments and feedback on previous
versions of this work.
article_processing_charge: No
author:
- first_name: Alkida
full_name: Balliu, Alkida
last_name: Balliu
- first_name: Juho
full_name: Hirvonen, Juho
last_name: Hirvonen
- first_name: Darya
full_name: Melnyk, Darya
last_name: Melnyk
- first_name: Dennis
full_name: Olivetti, Dennis
last_name: Olivetti
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
citation:
ama: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local mending.
In: Parter M, ed. International Colloquium on Structural Information and Communication
Complexity. Vol 13298. LNCS. Springer Nature; 2022:1-20. doi:10.1007/978-3-031-09993-9_1'
apa: 'Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., & Suomela,
J. (2022). Local mending. In M. Parter (Ed.), International Colloquium on Structural
Information and Communication Complexity (Vol. 13298, pp. 1–20). Paderborn,
Germany: Springer Nature. https://doi.org/10.1007/978-3-031-09993-9_1'
chicago: Balliu, Alkida, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki,
and Jukka Suomela. “Local Mending.” In International Colloquium on Structural
Information and Communication Complexity, edited by Merav Parter, 13298:1–20.
LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-09993-9_1.
ieee: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, and J. Suomela,
“Local mending,” in International Colloquium on Structural Information and
Communication Complexity, Paderborn, Germany, 2022, vol. 13298, pp. 1–20.
ista: 'Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. 2022. Local
mending. International Colloquium on Structural Information and Communication
Complexity. SIROCCO: Structural Information and Communication ComplexityLNCS vol.
13298, 1–20.'
mla: Balliu, Alkida, et al. “Local Mending.” International Colloquium on Structural
Information and Communication Complexity, edited by Merav Parter, vol. 13298,
Springer Nature, 2022, pp. 1–20, doi:10.1007/978-3-031-09993-9_1.
short: A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J. Suomela, in:,
M. Parter (Ed.), International Colloquium on Structural Information and Communication
Complexity, Springer Nature, 2022, pp. 1–20.
conference:
end_date: 2022-06-29
location: Paderborn, Germany
name: 'SIROCCO: Structural Information and Communication Complexity'
start_date: 2022-06-27
date_created: 2022-07-31T22:01:49Z
date_published: 2022-06-25T00:00:00Z
date_updated: 2023-08-03T12:16:29Z
day: '25'
department:
- _id: DaAl
doi: 10.1007/978-3-031-09993-9_1
ec_funded: 1
editor:
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
external_id:
arxiv:
- '2102.08703'
isi:
- '000876977400001'
intvolume: ' 13298'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2102.08703
month: '06'
oa: 1
oa_version: Preprint
page: 1-20
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: International Colloquium on Structural Information and Communication
Complexity
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031099922'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Local mending
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13298
year: '2022'
...
---
_id: '10218'
abstract:
- lang: eng
text: 'Let G be a graph on n nodes. In the stochastic population protocol model,
a collection of n indistinguishable, resource-limited nodes collectively solve
tasks via pairwise interactions. In each interaction, two randomly chosen neighbors
first read each other’s states, and then update their local states. A rich line
of research has established tight upper and lower bounds on the complexity of
fundamental tasks, such as majority and leader election, in this model, when G
is a clique. Specifically, in the clique, these tasks can be solved fast, i.e.,
in n polylog n pairwise interactions, with high probability, using at most polylog
n states per node. In this work, we consider the more general setting where G
is an arbitrary graph, and present a technique for simulating protocols designed
for fully-connected networks in any connected regular graph. Our main result is
a simulation that is efficient on many interesting graph families: roughly, the
simulation overhead is polylogarithmic in the number of nodes, and quadratic in
the conductance of the graph. As an example, this implies that, in any regular
graph with conductance φ, both leader election and exact majority can be solved
in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at
most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient
population protocols for leader election and exact majority on graphs with good
expansion properties.'
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 840605.
alternative_title:
- LIPIcs
article_number: '43'
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: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Gelashvili R, Rybicki J. Brief announcement: Fast graphical
population protocols. In: 35th International Symposium on Distributed Computing.
Vol 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.43'
apa: 'Alistarh, D.-A., Gelashvili, R., & Rybicki, J. (2021). Brief announcement:
Fast graphical population protocols. In 35th International Symposium on Distributed
Computing (Vol. 209). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.43'
chicago: 'Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Brief Announcement:
Fast Graphical Population Protocols.” In 35th International Symposium on Distributed
Computing, Vol. 209. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
https://doi.org/10.4230/LIPIcs.DISC.2021.43.'
ieee: 'D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Brief announcement: Fast
graphical population protocols,” in 35th International Symposium on Distributed
Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Alistarh D-A, Gelashvili R, Rybicki J. 2021. Brief announcement: Fast graphical
population protocols. 35th International Symposium on Distributed Computing. DISC:
Distributed Computing , LIPIcs, vol. 209, 43.'
mla: 'Alistarh, Dan-Adrian, et al. “Brief Announcement: Fast Graphical Population
Protocols.” 35th International Symposium on Distributed Computing, vol.
209, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.DISC.2021.43.'
short: D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, 35th International Symposium
on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing '
start_date: 2021-10-04
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2023-02-21T09:24:08Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.43
ec_funded: 1
external_id:
arxiv:
- '2102.08808'
file:
- access_level: open_access
checksum: fd2a690f6856d21247e9aa952b0e2885
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T08:16:44Z
date_updated: 2021-11-12T08:16:44Z
file_id: '10274'
file_name: 2021_LIPIcsDISC_Alistarh.pdf
file_size: 534219
relation: main_file
success: 1
file_date_updated: 2021-11-12T08:16:44Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Fast graphical population protocols'
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: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '10219'
abstract:
- lang: eng
text: We show that any algorithm that solves the sinkless orientation problem in
the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported
LOCAL is at least as strong as the usual LOCAL model, and as a corollary this
also gives a new, short and elementary proof that shows that the round complexity
of the sinkless orientation problem in the deterministic LOCAL model is Ω(log
n).
acknowledgement: "Janne H. Korhonen: Project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No 805223 ScaleML). Ami Paz: We acknowledge the Austrian
Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Stefan Schmid: Research
supported by the Austrian Science Fund (FWF) project ADVISE, I 4800-N, 2020-2023.\r\n"
alternative_title:
- LIPIcs
article_number: '58'
article_processing_charge: No
author:
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Ami
full_name: Paz, Ami
last_name: Paz
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
citation:
ama: 'Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. Brief announcement: Sinkless
orientation is hard also in the supported LOCAL model. In: 35th International
Symposium on Distributed Computing. Vol 209. Schloss Dagstuhl - Leibniz Zentrum
für Informatik; 2021. doi:10.4230/LIPIcs.DISC.2021.58'
apa: 'Korhonen, J., Paz, A., Rybicki, J., Schmid, S., & Suomela, J. (2021).
Brief announcement: Sinkless orientation is hard also in the supported LOCAL model.
In 35th International Symposium on Distributed Computing (Vol. 209). Freiburg,
Germany: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.58'
chicago: 'Korhonen, Janne, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela.
“Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL
Model.” In 35th International Symposium on Distributed Computing, Vol.
209. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.58.'
ieee: 'J. Korhonen, A. Paz, J. Rybicki, S. Schmid, and J. Suomela, “Brief announcement:
Sinkless orientation is hard also in the supported LOCAL model,” in 35th International
Symposium on Distributed Computing, Freiburg, Germany, 2021, vol. 209.'
ista: 'Korhonen J, Paz A, Rybicki J, Schmid S, Suomela J. 2021. Brief announcement:
Sinkless orientation is hard also in the supported LOCAL model. 35th International
Symposium on Distributed Computing. DISC: Distributed Computing , LIPIcs, vol.
209, 58.'
mla: 'Korhonen, Janne, et al. “Brief Announcement: Sinkless Orientation Is Hard
Also in the Supported LOCAL Model.” 35th International Symposium on Distributed
Computing, vol. 209, 58, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021, doi:10.4230/LIPIcs.DISC.2021.58.'
short: J. Korhonen, A. Paz, J. Rybicki, S. Schmid, J. Suomela, in:, 35th International
Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz Zentrum für Informatik,
2021.
conference:
end_date: 2021-10-08
location: Freiburg, Germany
name: 'DISC: Distributed Computing '
start_date: 2021-10-04
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-04T00:00:00Z
date_updated: 2021-11-12T09:37:18Z
day: '04'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2021.58
ec_funded: 1
external_id:
arxiv:
- '2108.02655'
file:
- access_level: open_access
checksum: c43188dc2070bbd2bf5fd6fdaf9ce36d
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-12T08:27:42Z
date_updated: 2021-11-12T08:27:42Z
file_id: '10275'
file_name: 2021_LIPIcsDISC_Korhonen.pdf
file_size: 474242
relation: main_file
success: 1
file_date_updated: 2021-11-12T08:27:42Z
has_accepted_license: '1'
intvolume: ' 209'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 35th International Symposium on Distributed Computing
publication_identifier:
isbn:
- 9-783-9597-7210-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Sinkless orientation is hard also in the supported LOCAL
model'
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: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 209
year: '2021'
...
---
_id: '9823'
abstract:
- lang: eng
text: "Approximate agreement is one of the few variants of consensus that can be
solved in a wait-free manner in asynchronous systems where processes communicate
by reading and writing to shared memory. In this work, we consider a natural generalisation
of approximate agreement on arbitrary undirected connected graphs. Each process
is given a vertex of the graph as input and, if non-faulty, must output a vertex
such that\r\nall the outputs are within distance 1 of one another, and\r\n\r\neach
output value lies on a shortest path between two input values.\r\n\r\nFrom prior
work, it is known that there is no wait-free algorithm among \U0001D45B≥3 processes
for this problem on any cycle of length \U0001D450≥4 , by reduction from 2-set
agreement (Castañeda et al. 2018).\r\n\r\nIn this work, we investigate the solvability
and complexity of this task on general graphs. We give a new, direct proof of
the impossibility of approximate agreement on cycles of length \U0001D450≥4
, via a generalisation of Sperner’s Lemma to convex polygons. We also extend the
reduction from 2-set agreement to a larger class of graphs, showing that approximate
agreement on these graphs is unsolvable. On the positive side, we present a wait-free
algorithm for a class of graphs that properly contains the class of chordal graphs."
alternative_title:
- LNCS
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: Faith
full_name: Ellen, Faith
last_name: Ellen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs.
In: Structural Information and Communication Complexity. Vol 12810. Springer
Nature; 2021:87-105. doi:10.1007/978-3-030-79527-6_6'
apa: 'Alistarh, D.-A., Ellen, F., & Rybicki, J. (2021). Wait-free approximate
agreement on graphs. In Structural Information and Communication Complexity
(Vol. 12810, pp. 87–105). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_6'
chicago: Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate
Agreement on Graphs.” In Structural Information and Communication Complexity,
12810:87–105. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_6.
ieee: D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement
on graphs,” in Structural Information and Communication Complexity, Wrocław,
Poland, 2021, vol. 12810, pp. 87–105.
ista: 'Alistarh D-A, Ellen F, Rybicki J. 2021. Wait-free approximate agreement on graphs.
Structural Information and Communication Complexity. SIROCCO: Structural Information
and Communication Complexity, LNCS, vol. 12810, 87–105.'
mla: Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Structural
Information and Communication Complexity, vol. 12810, Springer Nature, 2021,
pp. 87–105, doi:10.1007/978-3-030-79527-6_6.
short: D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication
Complexity, Springer Nature, 2021, pp. 87–105.
conference:
end_date: 2021-07-01
location: Wrocław, Poland
name: 'SIROCCO: Structural Information and Communication Complexity'
start_date: 2021-06-28
date_created: 2021-08-08T22:01:29Z
date_published: 2021-06-20T00:00:00Z
date_updated: 2023-02-23T14:09:49Z
day: '20'
department:
- _id: DaAl
doi: 10.1007/978-3-030-79527-6_6
external_id:
arxiv:
- '2103.08949'
intvolume: ' 12810'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2103.08949
month: '06'
oa: 1
oa_version: Preprint
page: 87-105
publication: Structural Information and Communication Complexity
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030795269'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Wait-free approximate agreement on graphs
type: conference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 12810
year: '2021'
...
---
_id: '10854'
abstract:
- lang: eng
text: "Consider a distributed task where the communication network is fixed but
the local inputs given to the nodes of the distributed system may change over
time. In this work, we explore the following question: if some of the local inputs
change, can an existing solution be updated efficiently, in a dynamic and distributed
manner?\r\nTo address this question, we define the batch dynamic CONGEST model
in which we are given a bandwidth-limited communication network and a dynamic
edge labelling defines the problem input. The task is to maintain a solution to
a graph problem on the labelled graph under batch changes. We investigate, when
a batch of alpha edge label changes arrive, - how much time as a function of alpha
we need to update an existing solution, and - how much information the nodes have
to keep in local memory between batches in order to update the solution quickly.\r\nOur
work lays the foundations for the theory of input-dynamic distributed network
algorithms. We give a general picture of the complexity landscape in this model,
design both universal algorithms and algorithms for concrete problems, and present
a general framework for lower bounds. The diverse time complexity of our model
spans from constant time, through time polynomial in alpha, and to alpha time,
which we show to be enough for any task."
acknowledgement: We thank Jukka Suomela for discussions. We also thank our shepherd
Mohammad Hajiesmaili and the reviewers for their time and suggestions on how to
improve the paper. This project has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska–Curie grant agreement No. 840605,
from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024,
and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.
article_processing_charge: No
author:
- first_name: Klaus-Tycho
full_name: Foerster, Klaus-Tycho
last_name: Foerster
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Ami
full_name: Paz, Ami
last_name: Paz
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed
algorithms for communication networks. In: Abstract Proceedings of the 2021
ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer
Systems. Association for Computing Machinery; 2021:71-72. doi:10.1145/3410220.3453923'
apa: 'Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021).
Input-dynamic distributed algorithms for communication networks. In Abstract
Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement
and Modeling of Computer Systems (pp. 71–72). Virtual, Online: Association
for Computing Machinery. https://doi.org/10.1145/3410220.3453923'
chicago: Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan
Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” In
Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference
on Measurement and Modeling of Computer Systems, 71–72. Association for Computing
Machinery, 2021. https://doi.org/10.1145/3410220.3453923.
ieee: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic
distributed algorithms for communication networks,” in Abstract Proceedings
of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling
of Computer Systems, Virtual, Online, 2021, pp. 71–72.
ista: 'Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic
distributed algorithms for communication networks. Abstract Proceedings of the
2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of
Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling
of Computer Systems, 71–72.'
mla: Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication
Networks.” Abstract Proceedings of the 2021 ACM SIGMETRICS / International
Conference on Measurement and Modeling of Computer Systems, Association for
Computing Machinery, 2021, pp. 71–72, doi:10.1145/3410220.3453923.
short: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, in:, Abstract
Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement
and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp.
71–72.
conference:
end_date: 2021-06-18
location: Virtual, Online
name: 'SIGMETRICS: International Conference on Measurement and Modeling of Computer
Systems'
start_date: 2021-06-14
date_created: 2022-03-18T08:48:41Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2023-09-26T10:40:55Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3410220.3453923
ec_funded: 1
external_id:
arxiv:
- '2005.07637'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.07637
month: '05'
oa: 1
oa_version: Preprint
page: 71-72
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference
on Measurement and Modeling of Computer Systems
publication_identifier:
isbn:
- '9781450380720'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '10855'
relation: extended_version
status: public
scopus_import: '1'
status: public
title: Input-dynamic distributed algorithms for communication networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10855'
abstract:
- lang: eng
text: 'Consider a distributed task where the communication network is fixed but
the local inputs given to the nodes of the distributed system may change over
time. In this work, we explore the following question: if some of the local inputs
change, can an existing solution be updated efficiently, in a dynamic and distributed
manner? To address this question, we define the batch dynamic \congest model in
which we are given a bandwidth-limited communication network and a dynamic edge
labelling defines the problem input. The task is to maintain a solution to a graph
problem on the labeled graph under batch changes. We investigate, when a batch
of α edge label changes arrive, \beginitemize \item how much time as a function
of α we need to update an existing solution, and \item how much information the
nodes have to keep in local memory between batches in order to update the solution
quickly. \enditemize Our work lays the foundations for the theory of input-dynamic
distributed network algorithms. We give a general picture of the complexity landscape
in this model, design both universal algorithms and algorithms for concrete problems,
and present a general framework for lower bounds. In particular, we derive non-trivial
upper bounds for two selected, contrasting problems: maintaining a minimum spanning
tree and detecting cliques.'
acknowledgement: "We thank Jukka Suomela for discussions. We also thank our shepherd
Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how
to improve the paper. This project\r\nhas received funding from the European Research
Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation
programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon
2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant
agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project
WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE
SCIENCE project P 33775-N."
article_processing_charge: No
article_type: original
author:
- first_name: Klaus-Tycho
full_name: Foerster, Klaus-Tycho
last_name: Foerster
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Ami
full_name: Paz, Ami
last_name: Paz
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed
algorithms for communication networks. Proceedings of the ACM on Measurement
and Analysis of Computing Systems. 2021;5(1):1-33. doi:10.1145/3447384
apa: Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021).
Input-dynamic distributed algorithms for communication networks. Proceedings
of the ACM on Measurement and Analysis of Computing Systems. Association for
Computing Machinery. https://doi.org/10.1145/3447384
chicago: Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan
Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” Proceedings
of the ACM on Measurement and Analysis of Computing Systems. Association for
Computing Machinery, 2021. https://doi.org/10.1145/3447384.
ieee: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic
distributed algorithms for communication networks,” Proceedings of the ACM
on Measurement and Analysis of Computing Systems, vol. 5, no. 1. Association
for Computing Machinery, pp. 1–33, 2021.
ista: Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic
distributed algorithms for communication networks. Proceedings of the ACM on Measurement
and Analysis of Computing Systems. 5(1), 1–33.
mla: Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication
Networks.” Proceedings of the ACM on Measurement and Analysis of Computing
Systems, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33,
doi:10.1145/3447384.
short: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of
the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.
date_created: 2022-03-18T09:10:27Z
date_published: 2021-03-01T00:00:00Z
date_updated: 2023-09-26T10:40:55Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3447384
ec_funded: 1
external_id:
arxiv:
- '2005.07637'
intvolume: ' 5'
issue: '1'
keyword:
- Computer Networks and Communications
- Hardware and Architecture
- Safety
- Risk
- Reliability and Quality
- Computer Science (miscellaneous)
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.07637
month: '03'
oa: 1
oa_version: Preprint
page: 1-33
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: Proceedings of the ACM on Measurement and Analysis of Computing Systems
publication_identifier:
issn:
- 2476-1249
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '10854'
relation: shorter_version
status: public
scopus_import: '1'
status: public
title: Input-dynamic distributed algorithms for communication networks
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2021'
...
---
_id: '9678'
abstract:
- lang: eng
text: We introduce a new graph problem, the token dropping game, and we show how
to solve it efficiently in a distributed setting. We use the token dropping game
as a tool to design an efficient distributed algorithm for stable orientations
and more generally for locally optimal semi-matchings. The prior work by Czygrinow
et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum
degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ).
For the more general problem of locally optimal semi-matchings, the prior upper
bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement
for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
acknowledgement: We thank Orr Fischer, Juho Hirvonen, and Tuomo Lempiäinen for valuable
discussions. This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No. 840605.
article_processing_charge: No
author:
- first_name: Sebastian
full_name: Brandt, Sebastian
last_name: Brandt
- first_name: Barbara
full_name: Keller, Barbara
last_name: Keller
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Jara
full_name: Uitto, Jara
last_name: Uitto
citation:
ama: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Efficient load-balancing
through distributed token dropping. In: Annual ACM Symposium on Parallelism
in Algorithms and Architectures. ; 2021:129-139. doi:10.1145/3409964.3461785'
apa: Brandt, S., Keller, B., Rybicki, J., Suomela, J., & Uitto, J. (2021). Efficient
load-balancing through distributed token dropping. In Annual ACM Symposium
on Parallelism in Algorithms and Architectures (pp. 129–139). Virtual Event,
United States. https://doi.org/10.1145/3409964.3461785
chicago: Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara
Uitto. “Efficient Load-Balancing through Distributed Token Dropping.” In Annual
ACM Symposium on Parallelism in Algorithms and Architectures, 129–39, 2021.
https://doi.org/10.1145/3409964.3461785.
ieee: S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Efficient load-balancing
through distributed token dropping,” in Annual ACM Symposium on Parallelism
in Algorithms and Architectures, Virtual Event, United States, 2021, pp.
129–139.
ista: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2021. Efficient load-balancing
through distributed token dropping. Annual ACM Symposium on Parallelism in Algorithms
and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures
, 129–139.'
mla: Brandt, Sebastian, et al. “Efficient Load-Balancing through Distributed Token
Dropping.” Annual ACM Symposium on Parallelism in Algorithms and Architectures,
2021, pp. 129–39, doi:10.1145/3409964.3461785.
short: S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, Annual ACM Symposium
on Parallelism in Algorithms and Architectures, 2021, pp. 129–139.
conference:
end_date: 2021-07-08
location: ' Virtual Event, United States'
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures '
start_date: 2021-07-06
date_created: 2021-07-18T22:01:22Z
date_published: 2021-07-06T00:00:00Z
date_updated: 2024-03-05T07:13:12Z
day: '06'
department:
- _id: DaAl
doi: 10.1145/3409964.3461785
ec_funded: 1
external_id:
arxiv:
- '2005.07761'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2005.07761
month: '07'
oa: 1
oa_version: Preprint
page: 129-139
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: Annual ACM Symposium on Parallelism in Algorithms and Architectures
publication_identifier:
isbn:
- '9781450380706'
publication_status: published
quality_controlled: '1'
related_material:
record:
- id: '15074'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Efficient load-balancing through distributed token dropping
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
year: '2021'
...
---
_id: '7224'
abstract:
- lang: eng
text: 'Habitat loss is one of the key drivers of the ongoing decline of biodiversity.
However, ecologists still argue about how fragmentation of habitat (independent
of habitat loss) affects species richness. The recently proposed habitat amount
hypothesis posits that species richness only depends on the total amount of habitat
in a local landscape. In contrast, empirical studies report contrasting patterns:
some find positive and others negative effects of fragmentation per se on species
richness. To explain this apparent disparity, we devise a stochastic, spatially
explicit model of competitive species communities in heterogeneous habitats. The
model shows that habitat loss and fragmentation have complex effects on species
diversity in competitive communities. When the total amount of habitat is large,
fragmentation per se tends to increase species diversity, but if the total amount
of habitat is small, the situation is reversed: fragmentation per se decreases
species diversity.'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Nerea
full_name: Abrego, Nerea
last_name: Abrego
- first_name: Otso
full_name: Ovaskainen, Otso
last_name: Ovaskainen
citation:
ama: Rybicki J, Abrego N, Ovaskainen O. Habitat fragmentation and species diversity
in competitive communities. Ecology Letters. 2020;23(3):506-517. doi:10.1111/ele.13450
apa: Rybicki, J., Abrego, N., & Ovaskainen, O. (2020). Habitat fragmentation
and species diversity in competitive communities. Ecology Letters. Wiley.
https://doi.org/10.1111/ele.13450
chicago: Rybicki, Joel, Nerea Abrego, and Otso Ovaskainen. “Habitat Fragmentation
and Species Diversity in Competitive Communities.” Ecology Letters. Wiley,
2020. https://doi.org/10.1111/ele.13450.
ieee: J. Rybicki, N. Abrego, and O. Ovaskainen, “Habitat fragmentation and species
diversity in competitive communities,” Ecology Letters, vol. 23, no. 3.
Wiley, pp. 506–517, 2020.
ista: Rybicki J, Abrego N, Ovaskainen O. 2020. Habitat fragmentation and species
diversity in competitive communities. Ecology Letters. 23(3), 506–517.
mla: Rybicki, Joel, et al. “Habitat Fragmentation and Species Diversity in Competitive
Communities.” Ecology Letters, vol. 23, no. 3, Wiley, 2020, pp. 506–17,
doi:10.1111/ele.13450.
short: J. Rybicki, N. Abrego, O. Ovaskainen, Ecology Letters 23 (2020) 506–517.
date_created: 2020-01-04T11:04:30Z
date_published: 2020-03-01T00:00:00Z
date_updated: 2023-09-05T16:04:30Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1111/ele.13450
ec_funded: 1
external_id:
isi:
- '000503625200001'
file:
- access_level: open_access
checksum: 372f67f2744f4b6049e9778364766c22
content_type: application/pdf
creator: dernst
date_created: 2020-02-14T12:02:50Z
date_updated: 2020-07-14T12:47:54Z
file_id: '7486'
file_name: 2020_EcologyLetters_Rybicki.pdf
file_size: 3005474
relation: main_file
file_date_updated: 2020-07-14T12:47:54Z
has_accepted_license: '1'
intvolume: ' 23'
isi: 1
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 506-517
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: Ecology Letters
publication_identifier:
eissn:
- 1461-0248
issn:
- 1461-023X
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Habitat fragmentation and species diversity in competitive communities
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 23
year: '2020'
...
---
_id: '15074'
abstract:
- lang: eng
text: We introduce a new graph problem, the token dropping game, and we show how
to solve it efficiently in a distributed setting. We use the token dropping game
as a tool to design an efficient distributed algorithm for the stable orientation
problem, which is a special case of the more general locally optimal semi-matching
problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal
semi-matching in O(Δ⁵) rounds in graphs of maximum degree Δ, which directly implies
an algorithm with the same runtime for stable orientations. We improve the runtime
to O(Δ⁴) for stable orientations and prove a lower bound of Ω(Δ) rounds.
alternative_title:
- LIPIcs
article_number: '40'
article_processing_charge: No
author:
- first_name: Sebastian
full_name: Brandt, Sebastian
last_name: Brandt
- first_name: Barbara
full_name: Keller, Barbara
last_name: Keller
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Jara
full_name: Uitto, Jara
last_name: Uitto
citation:
ama: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Brief announcement: Efficient
load-balancing through distributed token dropping. In: 34th International Symposium
on Distributed Computing. Vol 179. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2020. doi:10.4230/LIPIcs.DISC.2020.40'
apa: 'Brandt, S., Keller, B., Rybicki, J., Suomela, J., & Uitto, J. (2020).
Brief announcement: Efficient load-balancing through distributed token dropping.
In 34th International Symposium on Distributed Computing (Vol. 179). Virtual:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2020.40'
chicago: 'Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara
Uitto. “Brief Announcement: Efficient Load-Balancing through Distributed Token
Dropping.” In 34th International Symposium on Distributed Computing, Vol.
179. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.DISC.2020.40.'
ieee: 'S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Brief announcement:
Efficient load-balancing through distributed token dropping,” in 34th International
Symposium on Distributed Computing, Virtual, 2020, vol. 179.'
ista: 'Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2020. Brief announcement:
Efficient load-balancing through distributed token dropping. 34th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing,
LIPIcs, vol. 179, 40.'
mla: 'Brandt, Sebastian, et al. “Brief Announcement: Efficient Load-Balancing through
Distributed Token Dropping.” 34th International Symposium on Distributed Computing,
vol. 179, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.DISC.2020.40.'
short: S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, 34th International
Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020.
conference:
end_date: 2020-10-16
location: Virtual
name: 'DISC: Symposium on Distributed Computing'
start_date: 2020-10-12
date_created: 2024-03-05T07:09:12Z
date_published: 2020-10-07T00:00:00Z
date_updated: 2024-03-05T07:13:13Z
day: '07'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2020.40
external_id:
arxiv:
- '2005.07761'
file:
- access_level: open_access
checksum: 23e2d9321aef53092dc1e24a8ab82d72
content_type: application/pdf
creator: dernst
date_created: 2024-03-05T07:08:27Z
date_updated: 2024-03-05T07:08:27Z
file_id: '15075'
file_name: 2020_LIPIcs_Brandt.pdf
file_size: 303529
relation: main_file
success: 1
file_date_updated: 2024-03-05T07:08:27Z
has_accepted_license: '1'
intvolume: ' 179'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '10'
oa: 1
oa_version: Published Version
publication: 34th International Symposium on Distributed Computing
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '9678'
relation: later_version
status: public
scopus_import: '1'
status: public
title: 'Brief announcement: Efficient load-balancing through distributed token dropping'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 179
year: '2020'
...
---
_id: '6931'
abstract:
- lang: eng
text: "Consider a distributed system with n processors out of which f can be Byzantine
faulty. In the\r\napproximate agreement task, each processor i receives an input
value xi and has to decide on an\r\noutput value yi such that\r\n1. the output
values are in the convex hull of the non-faulty processors’ input values,\r\n2.
the output values are within distance d of each other.\r\n\r\n\r\nClassically,
the values are assumed to be from an m-dimensional Euclidean space, where m ≥
1.\r\nIn this work, we study the task in a discrete setting, where input values
with some structure\r\nexpressible as a graph. Namely, the input values are vertices
of a finite graph G and the goal is to\r\noutput vertices that are within distance
d of each other in G, but still remain in the graph-induced\r\nconvex hull of
the input values. For d = 0, the task reduces to consensus and cannot be solved
with\r\na deterministic algorithm in an asynchronous system even with a single
crash fault. For any d ≥ 1,\r\nwe show that the task is solvable in asynchronous
systems when G is chordal and n > (ω + 1)f,\r\nwhere ω is the clique number of
G. In addition, we give the first Byzantine-tolerant algorithm for a\r\nvariant
of lattice agreement. For synchronous systems, we show tight resilience bounds
for the exact\r\nvariants of these and related tasks over a large class of combinatorial
structures."
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Thomas
full_name: Nowak, Thomas
last_name: Nowak
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: 'Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: 33rd
International Symposium on Distributed Computing. Vol 146. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:10.4230/LIPICS.DISC.2019.29'
apa: 'Nowak, T., & Rybicki, J. (2019). Byzantine approximate agreement on graphs.
In 33rd International Symposium on Distributed Computing (Vol. 146, p.
29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.DISC.2019.29'
chicago: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
In 33rd International Symposium on Distributed Computing, 146:29:1--29:17.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.DISC.2019.29.
ieee: T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in 33rd
International Symposium on Distributed Computing, Budapest, Hungary, 2019,
vol. 146, p. 29:1--29:17.
ista: 'Nowak T, Rybicki J. 2019. Byzantine approximate agreement on graphs. 33rd
International Symposium on Distributed Computing. DISC: International Symposium
on Distributed Computing, LIPIcs, vol. 146, 29:1--29:17.'
mla: Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.”
33rd International Symposium on Distributed Computing, vol. 146, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:10.4230/LIPICS.DISC.2019.29.
short: T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17.
conference:
end_date: 2019-10-18
location: Budapest, Hungary
name: 'DISC: International Symposium on Distributed Computing'
start_date: 2019-10-14
date_created: 2019-10-08T12:41:38Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2021-01-12T08:09:38Z
ddc:
- '004'
department:
- _id: DaAl
doi: 10.4230/LIPICS.DISC.2019.29
ec_funded: 1
external_id:
arxiv:
- '1908.02743'
file:
- access_level: open_access
checksum: 2d2202f90c6ac991e50876451627c4b5
content_type: application/pdf
creator: jrybicki
date_created: 2019-10-08T12:47:19Z
date_updated: 2020-07-14T12:47:44Z
file_id: '6934'
file_name: LIPIcs-DISC-2019-29.pdf
file_size: 639378
relation: main_file
file_date_updated: 2020-07-14T12:47:44Z
has_accepted_license: '1'
intvolume: ' 146'
keyword:
- consensus
- approximate agreement
- Byzantine faults
- chordal graphs
- lattice agreement
language:
- iso: eng
oa: 1
oa_version: Published Version
page: 29:1--29:17
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 33rd International Symposium on Distributed Computing
publication_identifier:
eisbn:
- 978-3-95977-126-9
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Byzantine approximate agreement on graphs
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: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2019'
...
---
_id: '6936'
abstract:
- lang: eng
text: "A key challenge for community ecology is to understand to what extent observational
data can be used to infer the underlying community assembly processes. As different
processes can lead to similar or even identical patterns, statistical analyses
of non‐manipulative observational data never yield undisputable causal inference
on the underlying processes. Still, most empirical studies in community ecology
are based on observational data, and hence understanding under which circumstances
such data can shed light on assembly processes is a central concern for community
ecologists. We simulated a spatial agent‐based model that generates variation
in metacommunity dynamics across multiple axes, including the four classic metacommunity
paradigms as special cases. We further simulated a virtual ecologist who analysed
snapshot data sampled from the simulations using eighteen output metrics derived
from beta‐diversity and habitat variation indices, variation partitioning and
joint species distribution modelling. Our results indicated two main axes of variation
in the output metrics. The first axis of variation described whether the landscape
has patchy or continuous variation, and thus was essentially independent of the
properties of the species community. The second axis of variation related to the
level of predictability of the metacommunity. The most predictable communities
were niche‐based metacommunities inhabiting static landscapes with marked environmental
heterogeneity, such as metacommunities following the species sorting paradigm
or the mass effects paradigm. The most unpredictable communities were neutral‐based
metacommunities inhabiting dynamics landscapes with little spatial heterogeneity,
such as metacommunities following the neutral or patch sorting paradigms. The
output metrics from joint species distribution modelling yielded generally the
highest resolution to disentangle among the simulated scenarios. Yet, the different
types of statistical approaches utilized in this study carried complementary information,
and thus our results suggest that the most comprehensive evaluation of metacommunity
structure can be obtained by combining them.\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Otso
full_name: Ovaskainen, Otso
last_name: Ovaskainen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Nerea
full_name: Abrego, Nerea
last_name: Abrego
citation:
ama: Ovaskainen O, Rybicki J, Abrego N. What can observational data reveal about
metacommunity processes? Ecography. 2019;42(11):1877-1886. doi:10.1111/ecog.04444
apa: Ovaskainen, O., Rybicki, J., & Abrego, N. (2019). What can observational
data reveal about metacommunity processes? Ecography. Wiley. https://doi.org/10.1111/ecog.04444
chicago: Ovaskainen, Otso, Joel Rybicki, and Nerea Abrego. “What Can Observational
Data Reveal about Metacommunity Processes?” Ecography. Wiley, 2019. https://doi.org/10.1111/ecog.04444.
ieee: O. Ovaskainen, J. Rybicki, and N. Abrego, “What can observational data reveal
about metacommunity processes?,” Ecography, vol. 42, no. 11. Wiley, pp.
1877–1886, 2019.
ista: Ovaskainen O, Rybicki J, Abrego N. 2019. What can observational data reveal
about metacommunity processes? Ecography. 42(11), 1877–1886.
mla: Ovaskainen, Otso, et al. “What Can Observational Data Reveal about Metacommunity
Processes?” Ecography, vol. 42, no. 11, Wiley, 2019, pp. 1877–86, doi:10.1111/ecog.04444.
short: O. Ovaskainen, J. Rybicki, N. Abrego, Ecography 42 (2019) 1877–1886.
date_created: 2019-10-08T13:01:24Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2023-08-30T06:57:25Z
day: '01'
ddc:
- '577'
department:
- _id: DaAl
doi: 10.1111/ecog.04444
ec_funded: 1
external_id:
isi:
- '000486348700001'
file:
- access_level: open_access
checksum: 6c9fbbd5ea8ce10ae93e55ad560a7bf9
content_type: application/pdf
creator: jrybicki
date_created: 2019-10-08T13:07:44Z
date_updated: 2020-07-14T12:47:45Z
file_id: '6937'
file_name: ecog.04444.pdf
file_size: 1682718
relation: main_file
file_date_updated: 2020-07-14T12:47:45Z
has_accepted_license: '1'
intvolume: ' 42'
isi: 1
issue: '11'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1877-1886
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Ecography
publication_identifier:
eissn:
- 1600-0587
issn:
- 0906-7590
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: What can observational data reveal about metacommunity processes?
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 42
year: '2019'
...
---
_id: '6972'
abstract:
- lang: eng
text: 'We give fault-tolerant algorithms for establishing synchrony in distributed
systems in which each of thennodes has its own clock. Our algorithms operate in
a very strong fault model: we require self-stabilisation, i.e.,the initial state
of the system may be arbitrary, and there can be up to fJournal of the ACM. 2019;66(5). doi:10.1145/3339471
apa: Lenzen, C., & Rybicki, J. (2019). Self-stabilising Byzantine clock synchronisation
is almost as easy as consensus. Journal of the ACM. ACM. https://doi.org/10.1145/3339471
chicago: Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock
Synchronisation Is Almost as Easy as Consensus.” Journal of the ACM. ACM,
2019. https://doi.org/10.1145/3339471.
ieee: C. Lenzen and J. Rybicki, “Self-stabilising Byzantine clock synchronisation
is almost as easy as consensus,” Journal of the ACM, vol. 66, no. 5. ACM,
2019.
ista: Lenzen C, Rybicki J. 2019. Self-stabilising Byzantine clock synchronisation
is almost as easy as consensus. Journal of the ACM. 66(5), 32.
mla: Lenzen, Christoph, and Joel Rybicki. “Self-Stabilising Byzantine Clock Synchronisation
Is Almost as Easy as Consensus.” Journal of the ACM, vol. 66, no. 5, 32,
ACM, 2019, doi:10.1145/3339471.
short: C. Lenzen, J. Rybicki, Journal of the ACM 66 (2019).
date_created: 2019-10-24T17:12:48Z
date_published: 2019-09-01T00:00:00Z
date_updated: 2023-08-30T07:07:23Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3339471
ec_funded: 1
external_id:
arxiv:
- '1705.06173'
isi:
- '000496514100001'
file:
- access_level: open_access
checksum: 7e5d95c478e0e393f4927fcf7e48194e
content_type: application/pdf
creator: dernst
date_created: 2019-10-25T12:58:38Z
date_updated: 2020-07-14T12:47:46Z
file_id: '6975'
file_name: 2019_JACM_Lenzen.pdf
file_size: 2183085
relation: main_file
file_date_updated: 2020-07-14T12:47:46Z
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
issue: '5'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Journal of the ACM
publication_identifier:
issn:
- 0004-5411
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Self-stabilising Byzantine clock synchronisation is almost as easy as consensus
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 66
year: '2019'
...
---
_id: '6935'
abstract:
- lang: eng
text: "This paper investigates the power of preprocessing in the CONGEST model.
Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to
study the application of distributed algorithms in Software-Defined Networks (SDNs).
In this paper, we show that a large class of lower bounds in the CONGEST model
still hold in the SUPPORTED model, highlighting the robustness of these bounds.
This also raises the question how much does\r\npreprocessing help in the CONGEST
model."
article_processing_charge: No
author:
- first_name: Klaus-Tycho
full_name: Foerster, Klaus-Tycho
last_name: Foerster
- first_name: Janne
full_name: Korhonen, Janne
id: C5402D42-15BC-11E9-A202-CA2BE6697425
last_name: Korhonen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Foerster K-T, Korhonen J, Rybicki J, Schmid S. Does preprocessing help under
congestion? In: Proceedings of the 2019 ACM Symposium on Principles of Distributed
Computing. ACM; 2019:259-261. doi:10.1145/3293611.3331581'
apa: 'Foerster, K.-T., Korhonen, J., Rybicki, J., & Schmid, S. (2019). Does
preprocessing help under congestion? In Proceedings of the 2019 ACM Symposium
on Principles of Distributed Computing (pp. 259–261). Toronto, ON, Canada:
ACM. https://doi.org/10.1145/3293611.3331581'
chicago: Foerster, Klaus-Tycho, Janne Korhonen, Joel Rybicki, and Stefan Schmid.
“Does Preprocessing Help under Congestion?” In Proceedings of the 2019 ACM
Symposium on Principles of Distributed Computing, 259–61. ACM, 2019. https://doi.org/10.1145/3293611.3331581.
ieee: K.-T. Foerster, J. Korhonen, J. Rybicki, and S. Schmid, “Does preprocessing
help under congestion?,” in Proceedings of the 2019 ACM Symposium on Principles
of Distributed Computing, Toronto, ON, Canada, 2019, pp. 259–261.
ista: 'Foerster K-T, Korhonen J, Rybicki J, Schmid S. 2019. Does preprocessing help
under congestion? Proceedings of the 2019 ACM Symposium on Principles of Distributed
Computing. PODC: Symposium on Principles of Distributed Computing, 259–261.'
mla: Foerster, Klaus-Tycho, et al. “Does Preprocessing Help under Congestion?” Proceedings
of the 2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019,
pp. 259–61, doi:10.1145/3293611.3331581.
short: K.-T. Foerster, J. Korhonen, J. Rybicki, S. Schmid, in:, Proceedings of the
2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–261.
conference:
end_date: 2019-08-02
location: Toronto, ON, Canada
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2019-07-29
date_created: 2019-10-08T12:57:14Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-09-08T11:37:22Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3293611.3331581
ec_funded: 1
external_id:
arxiv:
- '1905.03012'
isi:
- '000570442000037'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1905.03012
month: '08'
oa: 1
oa_version: Preprint
page: 259-261
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9781450362177'
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Does preprocessing help under congestion?
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '43'
abstract:
- lang: eng
text: 'The initial amount of pathogens required to start an infection within a susceptible
host is called the infective dose and is known to vary to a large extent between
different pathogen species. We investigate the hypothesis that the differences
in infective doses are explained by the mode of action in the underlying mechanism
of pathogenesis: Pathogens with locally acting mechanisms tend to have smaller
infective doses than pathogens with distantly acting mechanisms. While empirical
evidence tends to support the hypothesis, a formal theoretical explanation has
been lacking. We give simple analytical models to gain insight into this phenomenon
and also investigate a stochastic, spatially explicit, mechanistic within-host
model for toxin-dependent bacterial infections. The model shows that pathogens
secreting locally acting toxins have smaller infective doses than pathogens secreting
diffusive toxins, as hypothesized. While local pathogenetic mechanisms require
smaller infective doses, pathogens with distantly acting toxins tend to spread
faster and may cause more damage to the host. The proposed model can serve as
a basis for the spatially explicit analysis of various virulence factors also
in the context of other problems in infection dynamics.'
acknowledgement: J.R. and J.V.A. were also supported by the Academy of Finland Grants
1273253 and 267541.
article_processing_charge: No
author:
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Eva
full_name: Kisdi, Eva
last_name: Kisdi
- first_name: Jani
full_name: Anttila, Jani
last_name: Anttila
citation:
ama: Rybicki J, Kisdi E, Anttila J. Model of bacterial toxin-dependent pathogenesis
explains infective dose. PNAS. 2018;115(42):10690-10695. doi:10.1073/pnas.1721061115
apa: Rybicki, J., Kisdi, E., & Anttila, J. (2018). Model of bacterial toxin-dependent
pathogenesis explains infective dose. PNAS. National Academy of Sciences.
https://doi.org/10.1073/pnas.1721061115
chicago: Rybicki, Joel, Eva Kisdi, and Jani Anttila. “Model of Bacterial Toxin-Dependent
Pathogenesis Explains Infective Dose.” PNAS. National Academy of Sciences,
2018. https://doi.org/10.1073/pnas.1721061115.
ieee: J. Rybicki, E. Kisdi, and J. Anttila, “Model of bacterial toxin-dependent
pathogenesis explains infective dose,” PNAS, vol. 115, no. 42. National
Academy of Sciences, pp. 10690–10695, 2018.
ista: Rybicki J, Kisdi E, Anttila J. 2018. Model of bacterial toxin-dependent pathogenesis
explains infective dose. PNAS. 115(42), 10690–10695.
mla: Rybicki, Joel, et al. “Model of Bacterial Toxin-Dependent Pathogenesis Explains
Infective Dose.” PNAS, vol. 115, no. 42, National Academy of Sciences,
2018, pp. 10690–95, doi:10.1073/pnas.1721061115.
short: J. Rybicki, E. Kisdi, J. Anttila, PNAS 115 (2018) 10690–10695.
date_created: 2018-12-11T11:44:19Z
date_published: 2018-10-02T00:00:00Z
date_updated: 2023-09-13T08:57:38Z
day: '02'
ddc:
- '570'
- '577'
department:
- _id: DaAl
doi: 10.1073/pnas.1721061115
ec_funded: 1
external_id:
isi:
- '000447491300057'
file:
- access_level: open_access
checksum: df7ac544a587c06b75692653b9fabd18
content_type: application/pdf
creator: dernst
date_created: 2019-04-09T08:02:50Z
date_updated: 2020-07-14T12:46:26Z
file_id: '6258'
file_name: 2018_PNAS_Rybicki.pdf
file_size: 4070777
relation: main_file
file_date_updated: 2020-07-14T12:46:26Z
has_accepted_license: '1'
intvolume: ' 115'
isi: 1
issue: '42'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 10690 - 10695
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: PNAS
publication_status: published
publisher: National Academy of Sciences
publist_id: '8011'
pubrep_id: '1063'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Model of bacterial toxin-dependent pathogenesis explains infective dose
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 115
year: '2018'
...
---
_id: '76'
abstract:
- lang: eng
text: 'Consider a fully-connected synchronous distributed system consisting of n
nodes, where up to f nodes may be faulty and every node starts in an arbitrary
initial state. In the synchronous C-counting problem, all nodes need to eventually
agree on a counter that is increased by one modulo C in each round for given C>1.
In the self-stabilising firing squad problem, the task is to eventually guarantee
that all non-faulty nodes have simultaneous responses to external inputs: if a
subset of the correct nodes receive an external “go” signal as input, then all
correct nodes should agree on a round (in the not-too-distant future) in which
to jointly output a “fire” signal. Moreover, no node should generate a “fire”
signal without some correct node having previously received a “go” signal as input.
We present a framework reducing both tasks to binary consensus at very small cost.
For example, we obtain a deterministic algorithm for self-stabilising Byzantine
firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation
and response time O(f), and message size O(log f). As our framework does not restrict
the type of consensus routines used, we also obtain efficient randomised solutions.'
article_processing_charge: Yes (via OA deal)
author:
- first_name: Christoph
full_name: Lenzen, Christoph
last_name: Lenzen
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
citation:
ama: Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads.
Distributed Computing. 2018. doi:10.1007/s00446-018-0342-6
apa: Lenzen, C., & Rybicki, J. (2018). Near-optimal self-stabilising counting
and firing squads. Distributed Computing. Springer. https://doi.org/10.1007/s00446-018-0342-6
chicago: Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting
and Firing Squads.” Distributed Computing. Springer, 2018. https://doi.org/10.1007/s00446-018-0342-6.
ieee: C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing
squads,” Distributed Computing. Springer, 2018.
ista: Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing
squads. Distributed Computing.
mla: Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting
and Firing Squads.” Distributed Computing, Springer, 2018, doi:10.1007/s00446-018-0342-6.
short: C. Lenzen, J. Rybicki, Distributed Computing (2018).
date_created: 2018-12-11T11:44:30Z
date_published: 2018-09-12T00:00:00Z
date_updated: 2023-09-13T09:01:06Z
day: '12'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/s00446-018-0342-6
external_id:
isi:
- '000475627800005'
file:
- access_level: open_access
checksum: 872db70bba9b401500abe3c6ae2f1a61
content_type: application/pdf
creator: dernst
date_created: 2018-12-17T14:21:22Z
date_updated: 2020-07-14T12:48:01Z
file_id: '5711'
file_name: 2018_DistributedComputing_Lenzen.pdf
file_size: 799337
relation: main_file
file_date_updated: 2020-07-14T12:48:01Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Distributed Computing
publication_status: published
publisher: Springer
publist_id: '7978'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Near-optimal self-stabilising counting and firing squads
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '6932'
abstract:
- lang: eng
text: "LCLs or locally checkable labelling problems (e.g. maximal independent set,
maximal matching, and vertex colouring) in the LOCAL model of computation are
very well-understood in cycles (toroidal 1-dimensional grids): every problem has
a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms
can be fully automated. This work develops the complexity theory of LCL problems
for toroidal 2-dimensional grids. The complexity classes are the same as in the
1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it
is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids.\r\nNevertheless,
if we correctly guess that the complexity of a problem is Θ(log* n), we can completely
automate the design of optimal algorithms. For any problem we can find an algorithm
that is of a normal form A' o Sk, where A' is a finite function, Sk is an algorithm
for finding a maximal independent set in kth power of the grid, and k is a constant.\r\nFinally,
partially with the help of automated design tools, we classify the complexity
of several concrete LCL problems related to colourings and orientations."
article_processing_charge: No
author:
- first_name: Sebastian
full_name: Brandt, Sebastian
last_name: Brandt
- first_name: Juho
full_name: Hirvonen, Juho
last_name: Hirvonen
- first_name: Janne H.
full_name: Korhonen, Janne H.
last_name: Korhonen
- first_name: Tuomo
full_name: Lempiäinen, Tuomo
last_name: Lempiäinen
- first_name: Patric R.J.
full_name: Östergård, Patric R.J.
last_name: Östergård
- first_name: Christopher
full_name: Purcell, Christopher
last_name: Purcell
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Przemysław
full_name: Uznański, Przemysław
last_name: Uznański
citation:
ama: 'Brandt S, Hirvonen J, Korhonen JH, et al. LCL problems on grids. In: ACM Press;
2017:101-110. doi:10.1145/3087801.3087833'
apa: 'Brandt, S., Hirvonen, J., Korhonen, J. H., Lempiäinen, T., Östergård, P. R.
J., Purcell, C., … Uznański, P. (2017). LCL problems on grids (pp. 101–110). Presented
at the PODC: Principles of Distributed Computing, Washington, DC, United States:
ACM Press. https://doi.org/10.1145/3087801.3087833'
chicago: Brandt, Sebastian, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen,
Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław
Uznański. “LCL Problems on Grids,” 101–10. ACM Press, 2017. https://doi.org/10.1145/3087801.3087833.
ieee: 'S. Brandt et al., “LCL problems on grids,” presented at the PODC:
Principles of Distributed Computing, Washington, DC, United States, 2017, pp.
101–110.'
ista: 'Brandt S, Hirvonen J, Korhonen JH, Lempiäinen T, Östergård PRJ, Purcell C,
Rybicki J, Suomela J, Uznański P. 2017. LCL problems on grids. PODC: Principles
of Distributed Computing, 101–110.'
mla: Brandt, Sebastian, et al. LCL Problems on Grids. ACM Press, 2017, pp.
101–10, doi:10.1145/3087801.3087833.
short: S. Brandt, J. Hirvonen, J.H. Korhonen, T. Lempiäinen, P.R.J. Östergård, C.
Purcell, J. Rybicki, J. Suomela, P. Uznański, in:, ACM Press, 2017, pp. 101–110.
conference:
end_date: 2017-07-27
location: Washington, DC, United States
name: 'PODC: Principles of Distributed Computing'
start_date: 2017-07-25
date_created: 2019-10-08T12:47:46Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2021-01-12T08:09:39Z
day: '01'
doi: 10.1145/3087801.3087833
extern: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 101-110
publication_identifier:
isbn:
- '9781450349925'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
status: public
title: LCL problems on grids
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...