Distributed Consensus with Finite Message Passing

Details Distributed Consensus with Finite Message Passing Distributed Consensus with Finite Message Passing

2010-06-09

arxiv.org/abs/1006.1727v2

Computer Science

Information Theory

5 pages, 5 figures, to be presented at ISIT 2010 (typos corrected)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Distributed Consensus with Finite Message Passing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed Consensus with Finite Message Passing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Consensus with Finite Message Passing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-39420