Brief Announcement: Temporal Locality in Online Algorithms

Maciej Pacut; Mahmoud Parham; Joel Rybicki; Stefan Schmid; Jukka Suomela; Aleksandr Tereshchenko

doi:10.4230/LIPIcs.DISC.2022.52

Brief Announcement: Temporal Locality in Online Algorithms

Maciej Pacut^*, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, Aleksandr Tereshchenko

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific

5 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	36th International Symposium on Distributed Computing, DISC 2022
Editors	Christian Scheideler
Publisher	Schloss Dagstuhl-Leibniz-Zentrum für Informatik
Number of pages	3
ISBN (Electronic)	9783959772556
DOIs	https://doi.org/10.4230/LIPIcs.DISC.2022.52
Publication status	Published - 1 Oct 2022
MoE publication type	B3 Non-refereed article in conference proceedings
Event	International Symposium on Distributed Computing - Augusta, United States Duration: 25 Oct 2022 → 27 Oct 2022 Conference number: 36

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl-Leibniz-Zentrum für Informatik
Volume	246
ISSN (Print)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Abbreviated title	DISC
Country/Territory	United States
City	Augusta
Period	25/10/2022 → 27/10/2022

Keywords

distributed algorithms
Online algorithms

Access to Document

10.4230/LIPIcs.DISC.2022.52

Temporal Locality in Online AlgorithmsFinal published version, 494 KBLicence: CC BY

SFX availability

Full text

Cite this

Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J., & Tereshchenko, A. (2022). Brief Announcement: Temporal Locality in Online Algorithms. In C. Scheideler (Ed.), 36th International Symposium on Distributed Computing, DISC 2022 [52] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 246). Schloss Dagstuhl-Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2022.52

@inproceedings{9bbad6f3a74944d2bfc30d1df55aa394,

title = "Brief Announcement: Temporal Locality in Online Algorithms",

abstract = "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.",

keywords = "distributed algorithms, Online algorithms",

author = "Maciej Pacut and Mahmoud Parham and Joel Rybicki and Stefan Schmid and Jukka Suomela and Aleksandr Tereshchenko",

note = "Funding Information: Funding This research has received funding from the German Research Foundation (DFG), grant 470029389 (FlexNets), 2021-2024, and the Marie Sk{\l}odowska-Curie grant agreement No. 840605. Publisher Copyright: {\textcopyright} Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko.; International Symposium on Distributed Computing, DISC ; Conference date: 25-10-2022 Through 27-10-2022",

year = "2022",

month = oct,

day = "1",

doi = "10.4230/LIPIcs.DISC.2022.52",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik",

editor = "Christian Scheideler",

booktitle = "36th International Symposium on Distributed Computing, DISC 2022",

address = "Germany",

}

Pacut, M, Parham, M, Rybicki, J, Schmid, S, Suomela, J & Tereshchenko, A 2022, Brief Announcement: Temporal Locality in Online Algorithms. in C Scheideler (ed.), 36th International Symposium on Distributed Computing, DISC 2022., 52, Leibniz International Proceedings in Informatics, LIPIcs, vol. 246, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Augusta, Georgia, United States, 25/10/2022. https://doi.org/10.4230/LIPIcs.DISC.2022.52

Brief Announcement: Temporal Locality in Online Algorithms. / Pacut, Maciej; Parham, Mahmoud; Rybicki, Joel et al.

36th International Symposium on Distributed Computing, DISC 2022. ed. / Christian Scheideler. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. 52 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 246).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific

TY - GEN

T1 - Brief Announcement: Temporal Locality in Online Algorithms

AU - Pacut, Maciej

AU - Parham, Mahmoud

AU - Rybicki, Joel

AU - Schmid, Stefan

AU - Suomela, Jukka

AU - Tereshchenko, Aleksandr

N1 - Conference code: 36

PY - 2022/10/1

Y1 - 2022/10/1

N2 - 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.

AB - 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.

KW - distributed algorithms

KW - Online algorithms

UR - http://www.scopus.com/inward/record.url?scp=85140928957&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.DISC.2022.52

DO - 10.4230/LIPIcs.DISC.2022.52

M3 - Conference contribution

AN - SCOPUS:85140928957

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 36th International Symposium on Distributed Computing, DISC 2022

A2 - Scheideler, Christian

PB - Schloss Dagstuhl-Leibniz-Zentrum für Informatik

T2 - International Symposium on Distributed Computing

Y2 - 25 October 2022 through 27 October 2022

ER -

Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. Brief Announcement: Temporal Locality in Online Algorithms. In Scheideler C, editor, 36th International Symposium on Distributed Computing, DISC 2022. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. 2022. 52. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.DISC.2022.52

Brief Announcement: Temporal Locality in Online Algorithms

Abstract

Publication series

Conference

Keywords

Access to Document

SFX availability

Other files and links

Fingerprint

Cite this