Computer Science
Fault-tolerant Snapshot Objects in Message Passing Systems
Document Type
Conference Paper
Abstract
The atomic snapshot object (ASO) can be seen as a generalization of the atomic read/write register. ASO divides the object into n segments such that each node can update its own segment, and instantaneously scan all segments of the object. ASO is a powerful data structure that has many important applications, such as update-query state machines, linearizable conflict-free replicated data types, generalized lattice agreement, and cryptocurrency as in the form of an asset transfer object. This paper studies ASO in asynchronous message passing systems and proposes a framework for implementing efficient fault-tolerant snapshot objects. Denote by D the maximum message delay and k the actual number of failures in an execution. Our framework derives two ASO algorithms: •A crash-tolerant ASO algorithm that achieves O(vk. D) time complexity for both update and scan operations, and achieves amortized constant time operations if there are O(vk) operations. •A Byzantine ASO algorithm that achieves O(k.D) time complexity for both update and scan operations, and achieves amortized constant time operations if there is no Byzantine node in a given execution. The framework can also be adapted to implement sequentially consistent snapshot objects (SSO) that complete scan operations locally without any communication, and have the same time complexlty for update onerations as in our ASO algorithms.
Publication Title
Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium, IPDPS 2022
Publication Date
2022
First Page
1129
Last Page
1139
ISBN
9781665481069
DOI
10.1109/IPDPS53621.2022.00113
Keywords
asynchrony, atomic snapshot object, byzantine failure, crash failure, sequential snapshot object
Repository Citation
Garg, Vijay K.; Kumar, Saptaparni; Tseng, Lewis; and Zheng, Xiong, "Fault-tolerant Snapshot Objects in Message Passing Systems" (2022). Computer Science. 105.
https://commons.clarku.edu/faculty_computer_sciences/105
APA Citation
Garg, V. K., Kumar, S., Tseng, L., & Zheng, X. (2022, May). Fault-tolerant Snapshot Objects in Message Passing Systems. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (pp. 1129-1139). IEEE.