Exploiting Markov Chains to Reach Approximate Agreement in Partially Connected Networks
Satish Srinivasan and Azad Azadmanesh
International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2007)
San Diego, California (USA), July 16-18, 2007
SPECTS_Summary
Abstract: The research in reaching Approximate Agreement (AA) for fully connected networks is relatively mature. In contrast, the literature survey of the AA problem for partially connected networks is evident of considerably less work. This is due to the fact that a node may not have a complete view of the global network, which makes it difficult to attain the convergence properties. The complexity of the problem is compounded in the presence of message dropouts, faults, and orchestrated attacks. This study investigates the AA problem for partially connected networks without node failures. The properties of Markov Chains are exploited to show the AA of values held by the nodes in the network. The results show that the number of rounds of message-exchange to reach a network-convergence depends on the distribution of values and is bound by m/2 , where m is the network diameter. The intension of this research is to potentially use the approach as a stepping-stone for future investigation of the AA problem in the presence of faults.
Index Terms: Markov Chains, Distributed Systems, Ad-Hoc Networks, Survivable Systems, Sensor Networks, Byzantine Agreement.