---
_id: '12164'
abstract:
- lang: eng
text: 'A shared-memory counter is a widely-used and well-studied concurrent object.
It supports two operations: An Inc operation that increases its value by 1 and
a Read operation that returns its current value. In Jayanti et al (SIAM J Comput,
30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case
step complexity of obstruction-free implementations, from read-write registers,
of a large class of shared objects that includes counters. The lower bound leaves
open the question of finding counter implementations with sub-linear amortized
step complexity. In this work, we address this gap. We show that n-process, wait-free
and linearizable counters can be implemented from read-write registers with O(log2n)
amortized step complexity. This is the first counter algorithm from read-write
registers that provides sub-linear amortized step complexity in executions of
arbitrary length. Since a logarithmic lower bound on the amortized step complexity
of obstruction-free counter implementations exists, our upper bound is within
a logarithmic factor of the optimal. The worst-case step complexity of the construction
remains linear, which is optimal. This is obtained thanks to a new max register
construction with O(logn) amortized step complexity in executions of arbitrary
length in which the value stored in the register does not grow too quickly. We
then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel
[1] in which we “plug” our max register implementation to show that it remains
linearizable while achieving O(log2n) amortized step complexity.'
acknowledgement: A preliminary version of this work appeared in DISC’19. Mirza Ahad
Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes
and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported
by the Israel Science Foundation (Grants 380/18 and 1425/22).
article_processing_charge: No
article_type: original
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Danny
full_name: Hendler, Danny
last_name: Hendler
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 2023;36:29-43. doi:10.1007/s00446-022-00439-5
apa: Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2023). Long-lived
counters with polylogarithmic amortized step complexity. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-022-00439-5
chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
“Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” Distributed
Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00439-5.
ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with
polylogarithmic amortized step complexity,” Distributed Computing, vol.
36. Springer Nature, pp. 29–43, 2023.
ista: Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 36, 29–43.
mla: Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized
Step Complexity.” Distributed Computing, vol. 36, Springer Nature, 2023,
pp. 29–43, doi:10.1007/s00446-022-00439-5.
short: M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023)
29–43.
date_created: 2023-01-12T12:10:08Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-16T08:39:36Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00446-022-00439-5
external_id:
isi:
- '000890138700001'
intvolume: ' 36'
isi: 1
keyword:
- Computational Theory and Mathematics
- Computer Networks and Communications
- Hardware and Architecture
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://drops.dagstuhl.de/opus/volltexte/2019/11310/
month: '03'
oa: 1
oa_version: Preprint
page: 29-43
publication: Distributed Computing
publication_identifier:
eissn:
- 1432-0452
issn:
- 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived counters with polylogarithmic amortized step complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_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
arxiv: 1
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'
...