Amortized Constant Round Atomic Snapshot in Message-Passing Systems
share
We study the lattice agreement (LA) and atomic snapshot problems in asynchronous message-passing systems where up to f nodes may crash. Our main result is a crash-tolerant atomic snapshot algorithm with amortized constant round complexity. To the best of our knowledge, the best prior result is given by Delporte et al. [TPDS, 18] with amortized O(n) complexity if there are more scans than updates. Our algorithm achieves amortized constant round if there are Ω(√(k)) operations, where k is the number of actual failures in an execution and is bounded by f. Moreover, when there is no failure, our algorithm has O(1) round complexity unconditionally. To achieve amortized constant round complexity, we devise a simple early-stopping lattice agreement algorithm and use it to "order" the update and scan operations for our snapshot object. Our LA algorithm has O(√(k)) round complexity. It is the first early-stopping LA algorithm in asynchronous systems.
READ FULL TEXT