---
_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: <i>36th International Symposium on
    Distributed Computing</i>. Vol 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2022. doi:<a href="https://doi.org/10.4230/LIPIcs.DISC.2022.52">10.4230/LIPIcs.DISC.2022.52</a>'
  apa: 'Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J., &#38; Tereshchenko,
    A. (2022). Brief announcement: Temporal locality in online algorithms. In <i>36th
    International Symposium on Distributed Computing</i> (Vol. 246). Augusta, GA,
    United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.DISC.2022.52">https://doi.org/10.4230/LIPIcs.DISC.2022.52</a>'
  chicago: 'Pacut, Maciej, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela,
    and Aleksandr Tereshchenko. “Brief Announcement: Temporal Locality in Online Algorithms.”
    In <i>36th International Symposium on Distributed Computing</i>, Vol. 246. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href="https://doi.org/10.4230/LIPIcs.DISC.2022.52">https://doi.org/10.4230/LIPIcs.DISC.2022.52</a>.'
  ieee: 'M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, and A. Tereshchenko,
    “Brief announcement: Temporal locality in online algorithms,” in <i>36th International
    Symposium on Distributed Computing</i>, 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.”
    <i>36th International Symposium on Distributed Computing</i>, vol. 246, 52, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href="https://doi.org/10.4230/LIPIcs.DISC.2022.52">10.4230/LIPIcs.DISC.2022.52</a>.'
  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: 2025-04-14T07:50:55Z
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'
...