An Incremental Distributed Algorithm for Computing Biconnected Components

This paper describes a distributed algorithm for computing the biconnected components of a dynamically changing graph. Our algorithm has a worst case communication complexity of O(b + c) messages for an edge insertion and O(b\u27 + c) messages for an edge removal, and a worst case time complexity of O(c) for both operations, where c is the maximum number of biconnected components in any of the connected components during the operation, b is the number of nodes in the biconnected component containing the new edge, and bprime is the number of nodes in the biconnected component in which the update request is being processed. The algorithm is presented in two stages. First, a serial algorithm is presented in which topology updates occur one at a time. Then, building on the serial algorithm, an algorithm is presented in which concurrent update requests are serialized within each connected component. The problem is motivated by the need to implement casual ordering of messages efifciently in a dynamically changing communication structure