---
_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. <i>Proceedings of the ACM on Measurement
    and Analysis of Computing Systems</i>. 2021;5(1):1-33. doi:<a href="https://doi.org/10.1145/3447384">10.1145/3447384</a>
  apa: Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., &#38; Schmid, S. (2021).
    Input-dynamic distributed algorithms for communication networks. <i>Proceedings
    of the ACM on Measurement and Analysis of Computing Systems</i>. Association for
    Computing Machinery. <a href="https://doi.org/10.1145/3447384">https://doi.org/10.1145/3447384</a>
  chicago: Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan
    Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings
    of the ACM on Measurement and Analysis of Computing Systems</i>. Association for
    Computing Machinery, 2021. <a href="https://doi.org/10.1145/3447384">https://doi.org/10.1145/3447384</a>.
  ieee: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic
    distributed algorithms for communication networks,” <i>Proceedings of the ACM
    on Measurement and Analysis of Computing Systems</i>, 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.” <i>Proceedings of the ACM on Measurement and Analysis of Computing
    Systems</i>, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33,
    doi:<a href="https://doi.org/10.1145/3447384">10.1145/3447384</a>.
  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'
...