Cyclic Storage for Fault-Tolerant Distributed Executions

Given a set V of active components in charge of a distributed execution, a storage scheme is a sequence B₀, B₁,..., B_b-1 of subsets of V, where successive global states are recorded. The subsets, also called blocks, have the same size and are scheduled according to some fixed and cyclic calendar of b steps. During the ith step, block B_i is selected. Each component takes a copy of its local state and sends it to one of the components in B_i, in such a way that each component stores (approximately) the same number of local states. Afterward, if a component of B_i crashes, all of its stored data is lost and the computation cannot continue. If there exists a block with no failed components in it, then a recent global state can be retrieved and the computation does not need to start over from the very beginning. The goal is to design storage schemes that tolerate as many crashes as possible, while trying to have each component participating in as few blocks as possible and, at the same time, working with large blocks (so that a component in a block stores a small number of local states). In this paper, several such schemes are described and compared in terms of these measures