03/08/2020

Long-lived snapshots with polylogarithmic amortized step complexity

Mirza Ahad Baig, Danny Hendler, Alessia Milani, Corentin Travers

Keywords: amortized step complexity, shared memory, max array, atomic snapshot

Abstract: We present the first deterministic wait-free long-lived snapshot algorithm, using only read and write operations, that guarantees polylogarithmic amortized step complexity in all executions. This is the first non-blocking snapshot algorithm, using reads and writes only, that has sub-linear amortized step complexity in executions of arbitrary length. The key to our construction is a novel implementation of a 2-component max array object which may be of independent interest.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at PODC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers