A Lyapunov Analysis of a Most Probable Path Finding Algorithm

Distributed information spreading algorithms are important building blocks in Aggregate Computing. We consider a special case, namely for finding a most probable path for message delivery from a set of sources to each device in a network. We formulate a Lyapunov function to prove its regional stability subject to initialization of estimated probabilities to the natural interval [0,1). We also prove that the algorithm converges in a finite time, and is ultimately bounded under persistent measurement errors. We provide tight bounds for convergence time, the ultimate bound, and the time for its attainment.