Abstract
Identifying articulation points (APs)—nodes whose failure disconnects a network—is critical for assessing network robustness. While centralized algorithms are well-established, distributed and dynamic environments pose significant challenges. This paper introduces a fully distributed, incremental algorithm that identifies APs in time-varying networks without requiring global topology knowledge. By replacing global resets with localized "change flag" propagation and an update-correct consensus mechanism, the approach achieves rapid convergence and preserves node privacy.
Introduction
In network science, biconnectivity is a key metric for robustness, representing a network's ability to remain connected despite a single node failure. Nodes that break this connectivity are termed articulation points or cut vertices. In static, centralized systems, these are easily identified using depth-first search (DFS) algorithms. However, modern networks such as robot swarms, power grids, and social networks are inherently distributed and dynamic.
Existing distributed methods often suffer from high communication overhead because they require a "global reset" whenever an edge is added or deleted. Furthermore, these methods often compromise privacy by requiring nodes to share local connection data. This paper addresses these limitations by proposing an incremental, privacy-preserving framework.
Methodology
The proposed framework utilizes a maximum consensus protocol where nodes maintain local states: a binary reachability vector and a shortest-path distance vector. The core of the system is a three-part incremental update mechanism.
Incremental Update Mechanism
- Change Flag Propagation: Upon an edge event (addition or deletion), incident nodes generate a "change flag" containing the event type, involved nodes, and a timestamp. This flag ripples through the network, signaling affected nodes to re-evaluate their states.
- Consensus Update Strategy: Nodes employ a modified max-consensus logic. When a flag arrives, the node distinguishes between "historical" reachability and "constraint" reachability (paths potentially broken by the change), preventing the algorithm from stalling on outdated information.
- Local State Correction: A "distance difference metric" allows nodes to determine if a local change invalidates their current shortest paths. If a deleted edge was not part of a node's shortest path, the node ignores the change, minimizing unnecessary recalculations.
Once local states stabilize, nodes apply a distributed criterion to determine their AP status based solely on distances to immediate neighbors.
Evaluation and Results
The algorithm was evaluated using synthetic simulations:
- 10-Node Network: Demonstrated recovery from single-edge deletions in 6 communication steps and additions in 5 steps.
- 20-Node Barabási-Albert (BA) Network: Simulated an "event storm" with high-frequency random changes. While state error increased during the storm, it plummeted to zero immediately once the topology stabilized.
The results confirm that the algorithm successfully identifies the correct set of articulation points in both single-change and high-frequency change scenarios once local stability is reached.
Discussion and Future Work
The "update-correct" philosophy ensures that while intermediate estimates may be inaccurate, the final converged result is guaranteed to be correct. Privacy is maintained because nodes only exchange distance vectors rather than adjacency lists, making global topology reconstruction impossible beyond a 2-hop neighborhood.
Future research will focus on extending this logic to directed networks, where reachability is non-reciprocal, and addressing asynchronous communication challenges such as packet loss and variable delays.
Summary updated