An Algorithm to Detect Stable Properties



In this section we describe in our framework the algorithm by Szymanski, Shi and Prywes (SSP's algorithm for short). We consider a distributed algorithm which terminates when all processes reach their local termination conditions. Each process is able to determine only its own termination condition. SSP's algorithm detects an instant in which the entire computation is achieved.



Let G be a graph, to each node v is associated a predicate P(v) and an integer a(v). Initially P(v) is false and a(v) is equal to -1.

Transformations of the value of a(v) are defined by the following rules.

Each local computation acts on the integer a(v0) associated to the vertex v0; the new value of a(v0) depends on values associated to vertices of B(v). More precisely, let v0 be a vertex and let {v1,...,vd} the set of vertices adjacent to v0.

Snapshots