Master of Science (MS)
First Committee Member
Ajoy Kumma Datta
Number of Pages
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.
Algorithm; Distributed; Fault; Fault Tolerance; Flow; Maximum; Self; Stabilizing; Tolerance
University of Nevada, Las Vegas
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to firstname.lastname@example.org and include clear identification of the work, preferably with URL.
Zhou, Yan, "A self-stabilizing distributed maximum flow algorithm" (1995). UNLV Retrospective Theses & Dissertations. 3142.