Distributed consensus with finite messaging

Debashis Dash; Ashutosh Sabharwal

doi:10.1109/ISIT.2010.5513279

Distributed consensus with finite messaging

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Pages	1763-1767
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2010.5513279
State	Published - 2010
Event	2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States Duration: Jun 13 2010 → Jun 18 2010

Publication series

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

Conference

Conference	2010 IEEE International Symposium on Information Theory, ISIT 2010
Country/Territory	United States
City	Austin, TX
Period	6/13/10 → 6/18/10

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2010.5513279

Cite this

Dash, D & Sabharwal, A 2010, Distributed consensus with finite messaging. in 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings., 5513279, IEEE International Symposium on Information Theory - Proceedings, pp. 1763-1767, 2010 IEEE International Symposium on Information Theory, ISIT 2010, Austin, TX, United States, 6/13/10. https://doi.org/10.1109/ISIT.2010.5513279

@inproceedings{6eb9dc63db394ab2a220b3a3f84af782,

title = "Distributed consensus with finite messaging",

abstract = "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.",

author = "Debashis Dash and Ashutosh Sabharwal",

year = "2010",

doi = "10.1109/ISIT.2010.5513279",

language = "English (US)",

isbn = "9781424469604",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "1763--1767",

booktitle = "2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings",

note = "2010 IEEE International Symposium on Information Theory, ISIT 2010 ; Conference date: 13-06-2010 Through 18-06-2010",

}

TY - GEN

T1 - Distributed consensus with finite messaging

AU - Dash, Debashis

AU - Sabharwal, Ashutosh

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77955677801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955677801&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2010.5513279

DO - 10.1109/ISIT.2010.5513279

M3 - Conference contribution

AN - SCOPUS:77955677801

SN - 9781424469604

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1763

EP - 1767

BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings

T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010

Y2 - 13 June 2010 through 18 June 2010

ER -

Distributed consensus with finite messaging

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this