A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
✍ Scribed by Toshio Nakata; Hiroshi Imahayashi; Masafumi Yamashita
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 123 KB
- Volume
- 35
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
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.