Randomized distributed online algorithms against adaptive offline adversaries

Joan Boyar*, Faith Ellen*, Kim S. Larsen*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

8 Downloads (Pure)


In the sequential setting, a decades-old fundamental result in online algorithms states that if there is a c-competitive randomized online algorithm against an adaptive, offline adversary, then there is a c-competitive deterministic algorithm. The adaptive, offline adversary is the strongest adversary among the ones usually considered, so the result states that if one has to be competitive against such a strong adversary, then randomization does not help. This implies that researchers do not consider randomization against an adaptive, offline adversary. We prove that in a distributed setting, this result does not necessarily hold, so randomization against an adaptive, offline adversary becomes interesting again.

Original languageEnglish
Article number105973
JournalInformation Processing letters
Number of pages4
Publication statusPublished - Sept 2020


  • Adaptive offline adversary
  • Distributed systems
  • Online algorithms
  • Randomized algorithms


Dive into the research topics of 'Randomized distributed online algorithms against adaptive offline adversaries'. Together they form a unique fingerprint.

Cite this