Randomized distributed online algorithms against adaptive offline adversaries

DOI10.1016/J.IPL.2020.105973MaRDI QIDQ783703zbMATH OpenOpenAlexFDO

Authors Joan Boyar, Faith Ellen, Kim S. Larsen

Publication date 4 August 2020

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2020.105973

zbMATH Keywords

online algorithmsrandomized algorithmsdistributed systemsadaptive offline adversary

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Distributed algorithms (68W15)

Recommendations

• On the power of randomization in on-line algorithms
• Randomized competitive algorithms for the list update problem
• On randomization in on-line computation.
• Randomization can be as helpful as a glimpse of the future in online computation
• Competitive randomized algorithms for nonuniform problems

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• A combined BIT and TIMESTAMP algorithm for the list update problem
• On the power of randomization in on-line algorithms
• Online algorithms. The state of the art
• Spreading Rumors Rapidly Despite an Adversary
• Two results on the list update problem

Cited in

(3)

• A reduction theorem for randomized distributed algorithms under weak adversaries
• On the power of randomization in on-line algorithms
• scientific article; zbMATH DE number 7650400 (Why is no real title available?)

This page was built for publication: Randomized distributed online algorithms against adaptive offline adversaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q783703)