We consider a distributed system in which agents communicate by sending messages and operate in synchronous rounds (roughly, all nodes update their internal state at the same frequency). There are many ways to model the communications on a distributed systems using a probabilistic approach. For example, in the PUSH model, in each round, each agent randomly picks an other agent and sends it a message.
We introduce the mod P-synchronization problem: each node holds a clock and all clock must eventually agree in spite of their arbitrary initialization. In this talk, we recall our previous work, which consists of a distributed algorithm, called SAP, which solves this problem in a non-probabilistic setting. Our goal is solving the same problem in a large range of probabilistic communication models. We show that the notion of dynamic diameter, which was used in our previous non-probabilistic work, is not suitable in this setting. We introduce the notion of probabilistic diameter which avoid those limitations.
