Distributed consensus with finite messaging

Debashis Dash, Ashutosh Sabharwal

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


Inspired by distributed resource allocation problems in dynamic topology networks, we initiate the study of distributed consensus with finite messaging passing. We first find a sufficient condition on the network graph for which no distributed protocol can guarantee a conflict-free allocation after R rounds of message passing. Secondly we fully characterize the conflict minimizing zero-round protocol for path graphs, namely random allocation, which partitions the graph into small conflict groups. Thirdly, we enumerate all one-round protocols for path graphs and show that the best one further partitions each of the smaller groups. Finally, we show that the number of conflicts decrease to zero as the number of available resources increase.

Original languageEnglish (US)
Title of host publication2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Number of pages5
StatePublished - 2010
Event2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8103


Conference2010 IEEE International Symposium on Information Theory, ISIT 2010
Country/TerritoryUnited States
CityAustin, TX

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Distributed consensus with finite messaging'. Together they form a unique fingerprint.

Cite this