Felix Gärtner: Fault-tolerant Weak-consistency Replication through Self-stabilization. Diploma thesis DA-BS-1997-06, Department of Computer Science, Darmstadt University of Technology, Germany, December 1997 (in German).
Abstract
In this thesis a family of novel distributed algorithms aimed at performing weak-consistency replication in a highly fault-tolerant manner is presented. The fault-tolerance is achieved by following the paradigm of self-stabilization which was introduced by Dijkstra in 1974. The algorithms are fully distributed in the sense that all nodes run the same algorithm in a message-passing environment (only unique node identities are required) and all nodes have to know the approximate size of the network. Because the algorithms are self-stabilizing, they can tolerate any form of transient failures and also a limited number of permanent failures (as long as no network partitions occur). The drawback from using the paradigm is that the fault-tolerance is non-masking and that network nodes can thus be subject of a limited amount of errorneous behaviour once failures occur. Theoretical analysis and simulation results suggest that these algorithms perform well compared to existing solutions to the problem of weak-consistency replication.