Brief Announcement: Temporal Locality in Online Algorithms

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



PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.52.pdf
  • Filesize: 0.5 MB
  • 3 pages

Document Identifiers

Author Details

Maciej Pacut
  • Technische Universität Berlin, Germany
Mahmoud Parham
  • Faculty of Computer Science, Universität Wien, Austria
Joel Rybicki
  • Institute of Science and Technology Austria, Klosterneuburg, Austria
Stefan Schmid
  • TU Berlin, German
  • Fraunhofer SIT, Berlin, Germany
Jukka Suomela
  • Aalto University, Espoo, Finland
Aleksandr Tereshchenko
  • Aalto University, Espoo, Finland

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. Marcin Bienkowski. Migrating and replicating data in networks. Computer Science-Research and Development, 27(3):169-179, 2012. Google Scholar
  3. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Google Scholar
  4. Shlomi Dolev. Self-Stabilization. MIT Press, 2000. Google Scholar
  5. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail