A SELF-STABILIZING ALGORITHM FOR THE MAXIMUM FLOW PROBLEM

The maximum flow problem is a fundamental problem in graph theory and combinatorial optimization with a variety of important applications. K nown distributed algorithms for this problem do not tolerate faults or adjust to dynamic changes in network topology. This paper presents a distributed self-stabilizing algorithm for the maximum flow problem. S tarting from an arbitrary state, the algorithm computes the maximum fl ow in an acyclic network in finitely many steps. Since the algorithm i s self-stabilizing, it is inherently tolerant to transient faults. It can automatically adjust to topology changes and to changes in other p arameters of the problem. The paper presents results obtained by exten sively experimenting with the algorithm. Two main observations based o n these results are (1) the algorithm requires fewer than n(2) moves f or almost all test cases and (2) the algorithm consistently performs a t least as well as a distributed implementation of the well-known Gold berg-Tarjan algorithm for almost all test cases. The paper ends with t he conjecture that the algorithm correctly computes a maximum flow eve n in networks that contain cycles.