---
_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
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. In: <i>Abstract Proceedings of the 2021
    ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer
    Systems</i>. Association for Computing Machinery; 2021:71-72. doi:<a href="https://doi.org/10.1145/3410220.3453923">10.1145/3410220.3453923</a>'
  apa: 'Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., &#38; Schmid, S. (2021).
    Input-dynamic distributed algorithms for communication networks. In <i>Abstract
    Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement
    and Modeling of Computer Systems</i> (pp. 71–72). Virtual, Online: Association
    for Computing Machinery. <a href="https://doi.org/10.1145/3410220.3453923">https://doi.org/10.1145/3410220.3453923</a>'
  chicago: Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan
    Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” In
    <i>Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference
    on Measurement and Modeling of Computer Systems</i>, 71–72. Association for Computing
    Machinery, 2021. <a href="https://doi.org/10.1145/3410220.3453923">https://doi.org/10.1145/3410220.3453923</a>.
  ieee: K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic
    distributed algorithms for communication networks,” in <i>Abstract Proceedings
    of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling
    of Computer Systems</i>, 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.” <i>Abstract Proceedings of the 2021 ACM SIGMETRICS / International
    Conference on Measurement and Modeling of Computer Systems</i>, Association for
    Computing Machinery, 2021, pp. 71–72, doi:<a href="https://doi.org/10.1145/3410220.3453923">10.1145/3410220.3453923</a>.
  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'
...