Order and Balance in Continuously-Fault-Tolerant Distributions of Objects

G. Coucopoulos, N. Goel, A. Nayak, and N. Santoro (Canada)


Distributed File, Fault Tolerance, Continuous K−Fault Tol erance, Protocols.


A distributed object systems is said to be K-tolerant if every object is available after the simultaneous failure of up to K nodes. The problem is that a K-tolerant system, after failures, is no longer K−tolerant; that is, subsequent failures may compromise the availability of the objects. A continuously K-tolerant system is one which starting from a K-tolerant configuration, after the failure of up to K nodes, reconfig ures itself so to remain K-tolerant. The existing protocols for maintaining continuous K-tolerance do so without regard to the resulting structure of the available data. For example, if the distributed set of objects was sorted, this ordering would be most likely lost after restructuring. Analogously, a bal anced distribution of the objects among the nodes might also be not achieved in the new distribution after reorganization. In this paper, we present a mechanism for maintaining con tinuous K-tolerance while keeping the load balanced and the objects sorted. The proposed solution uses minimum amount of replication and has a cost comparable to the one of the known unstructured solutions.

Important Links:

Go Back