Tight Bounds on Online Checkpointing Algorithms

DOI10.1145/3379543zbMATH Open1484.68335OpenAlexW3034127702WikidataQ114976837 ScholiaQ114976837MaRDI QIDQ4987449FDOQ4987449

Authors: Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, Adi Shamir 

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9017/

Recommendations

• Tight bounds on online checkpointing algorithms
• Approximately uniform online checkpointing with bounded memory
• New algorithms for optimal online checkpointing
• Approximately uniform online checkpointing
• The complexity of online memory checking
• On-line algorithms for locating checkpoints
• Stronger lower bounds for online ORAM

zbMATH Keywords

online algorithmscompetitive analysischeckpoints

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Cited In (4)

• On-line algorithms for locating checkpoints
• Tight bounds on online checkpointing algorithms
• Approximately uniform online checkpointing with bounded memory
• Approximately uniform online checkpointing

This page was built for publication: Tight Bounds on Online Checkpointing Algorithms

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