A self-stabilizing distributed maximum flow algorithm
Abstract
This thesis presents a self-stabilizing distributed maximum flow algorithm for a network G = (V, E), where V is a set of nodes in the network and E is a set of edges in the network. The algorithm has two phases: reset phase and preflow-push phase. Fault-tolerance is achieved by using a self-stabilizing paradigm that uses non-masking fault-tolerance embedded repetitions within the algorithm. Two techniques are used in the algorithm, Counter flushing is used to synchronize the network; both local checking and local correction are used to compute the maximum flow of the network. The algorithm handles catastrophic faults by weeding out false information in the network. A network can start with any arbitrary global state and will recover to a legal global state in finite number of steps. Lastly, the network guarantees to restore the legal configuration from any catastrophic faults.