Consensus -- with Limited Memory and Signalling

Add to your list(s) Download to your calendar using vCal

• Milan Vojnovic, Microsoft research Cambridge
• Thursday 16 October 2008, 16:00-17:00
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Neil Walton.

We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts other nodes and updates its current state based on the state communicated by the last contacted node. We assume that both signalling (the information exchanged at node contacts) and memory (computation state at each node) are limited and restrict our attention to systems where each node can contact any other node (i.e., complete graphs). It is well known that for systems with binary signalling and memory, the probability of reaching incorrect consensus is equal to the fraction of nodes that initially held the minority state. We show that extending both the signalling and memory by just one state dramatically improves the reliability and speed of reaching the correct consensus. Specifically, we show that the probability of error decays exponentially with the number of nodes N and the convergence time is logarithmic in N for large N. We also examine the case when the state is ternary and signalling is binary. The convergence of this system to consensus is again shown to be logarithmic in N for large N, and is therefore faster than purely binary systems. The type of distributed consensus problems that we study arises in a variety of applications including those of sensor networks and opinion formation in social networks – our results suggest that robust and efficient protocols can be built with rather limited signalling and memory.

This talk is part of the Optimization and Incentives Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Economics and Computer Science Talks
• Hanchen DaDaDash
• Interested Talks
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Optimization and Incentives Seminar
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.