Dynamic p-graphs for capturing the dynamics of distributed systems

The dynamics of a mobile dynamic distributed system depends on both the node mobility and the capacity of the underlying communication protocol. To qualify the dynamics of a distributed system, the family of dynamic p-graphs is introduced in this paper, constituting a finite set of dynamic graphs, each of them being a sequence of observed graphs, with the particularity that their edges allow transferring p messages. The family of dynamic p-graphs allows the characterization and the comparison of dynamic distributed systems of very different nature. It is also used to evaluate the ability of algorithms themselves to support a given dynamic distributed system.