Monitoring Stable Properties in Dynamic Peer-to-Peer Distributed Systems

Monitoring a distributed system to detect a stable property is an important problem with many applications. The problem is especially challenging for a

dynamic

distributed system because the set of processes in the system may change with time. In this paper, we present an efficient algorithm to determine whether a stable property has become true in a system in which processes can join and depart the system at any time. Our algorithm is based on maintaining a spanning tree of processes that are currently part of the system. The spanning tree, which is dynamically changing, is used to periodically collect local states of processes such that: (1) all local states in the collection are

consistent

with each other, and (2) the collection is

complete

, that is, it contains all local states that are necessary to evaluate the property and derive meaningful inferences about the system state.

Unlike existing algorithms for stable property detection in a dynamic environment, our algorithm is general in the sense that it can be used to evaluate

any

stable property. Further, it does not assume the existence of any permanent process. Processes can join and leave the system while the snapshot algorithm is in progress.