Randomized distributed online algorithms against adaptive offline adversaries

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

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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.

OriginalsprogEngelsk
Artikelnummer105973
TidsskriftInformation Processing letters
Vol/bind161
Antal sider4
ISSN0020-0190
DOI
StatusUdgivet - sep. 2020

Fingeraftryk

Dyk ned i forskningsemnerne om 'Randomized distributed online algorithms against adaptive offline adversaries'. Sammen danner de et unikt fingeraftryk.

Citationsformater