A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem

In this paper, we investigate a probabilistic local majority polling game on weighted directed graphs, keeping an application to the distributed agreement problem in mind. We formulate the game as a Markov chain, where an absorbing state corresponds to a system configuration that an agreement is achieved, and characterize on which graphs the game will eventually reach an absorbing state with probability 1. We then calculate, given a pair of an initial and an absorbing states, the absorbing probability that the game will reach the absorbing state, starting with the initial state. We finally demonstrate that regular graphs have a desirable property from the view of the distributed agreement application, by using the martingale theory. (C) 2000 John Wiley & Sons, Inc.