Exploiting Markov Chains to reach Approximate Agreement in partially connected networks

Satish M. Srinivasan, Azad H. Azadmanesh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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 approximate convergence of the values of the nodes in the network. The results show that the number of rounds of messageexchange to reach a network-convergence depends on the distribution of values held by the nodes 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.

Original languageEnglish (US)
Title of host publicationInternational Symposium on Performance Evaluation of Computer and Telecommunication Systems 2007, SPECTS'07, Part of the 2007 Summer Simulation Multiconference, SummerSim'07
Pages82-89
Number of pages8
StatePublished - 2007
EventInternational Symposium on Performance Evaluation of Computer and Telecommunication Systems 2007, SPECTS 2007, Part of the 2007 Summer Simulation Multiconference, SummerSim 2007 - San Diego, CA, United States
Duration: Jul 15 2007Jul 18 2007

Publication series

NameInternational Symposium on Performance Evaluation of Computer and Telecommunication Systems 2007, SPECTS'07, Part of the 2007 Summer Simulation Multiconference, SummerSim'07

Other

OtherInternational Symposium on Performance Evaluation of Computer and Telecommunication Systems 2007, SPECTS 2007, Part of the 2007 Summer Simulation Multiconference, SummerSim 2007
Country/TerritoryUnited States
CitySan Diego, CA
Period7/15/077/18/07

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Modeling and Simulation

Fingerprint

Dive into the research topics of 'Exploiting Markov Chains to reach Approximate Agreement in partially connected networks'. Together they form a unique fingerprint.

Cite this