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. Known distributed algorithms for this problem do not tolerate faults or adjust to dynamic changes in network topology. This paper presents the first distributed self-stabilizing algorithm for the maximum flow problem. Starting from an arbitrary state, the algorithm computes the maximum flow in a acyclic network in finitely many steps. Since the algorithm is self-stabilizing, it is inherently tolerant to transient faults and can automatically adjust to topology changes and to changes in other parameters of the problem. A slight modification of the original algorithm is also presented and it is conjectured that the new algorithm computes a maximum flow in arbitrary networks