LIPIcs.DISC.2022.52.pdf
- Filesize: 0.5 MB
- 3 pages
Document
Brief Announcement: Temporal Locality in Online Algorithms
Authors
Maciej Pacut 
,
Mahmoud Parham ,
Joel Rybicki ,
Stefan Schmid ,
Jukka Suomela ,
-
Part of:
Volume:
36th International Symposium on Distributed Computing (DISC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-10-17
File
Document Identifiers
Author Details
Cite As Get BibTex
Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko. Brief Announcement: Temporal Locality in Online Algorithms. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.52
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Online algorithms
- Theory of computation → Distributed computing models
Keywords
- Online algorithms
- distributed algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Dana Angluin. Local and global properties in networks of processors. In Proc. 12th Annual ACM Symposium on Theory of Computing (STOC 1980), 1980. URL: https://doi.org/10.1145/800141.804655.
-
Marcin Bienkowski. Migrating and replicating data in networks. Computer Science-Research and Development, 27(3):169-179, 2012.
-
Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
-
Shlomi Dolev. Self-Stabilization. MIT Press, 2000.
- Klaus-Tycho Foerster, Juho Hirvonen, Jukka Suomela, and Stefan Schmid. On the power of preprocessing in decentralized network optimization. In Proc. 28th IEEE Conference on Computer Communications (INFOCOM 2019), 2019. URL: https://doi.org/10.1109/INFOCOM.2019.8737382.