Tight Bounds on Online Checkpointing Algorithms

DOI10.1145/3379543MaRDI QIDQ4987449zbMATH OpenOpenAlexWikidataFDO

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/

zbMATH Keywords

checkpointscompetitive analysisonline algorithms

Mathematics Subject Classification ID

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

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

Cited in

(4)

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

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)