COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Consensus -- with Limited Memory and Signalling

## Consensus -- with Limited Memory and SignallingAdd 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. |
## Other listsCambridge Migration Research Network Faith & Belief Social Mobility: Chavs, NEETs and McJobs## Other talksSingle Cell Seminars (November) Volcanoes and Explosions The Hopkins Lecture 2018 - mTOR and Lysosomes in Growth Control Replication or exploration? Sequential design for stochastic simulation experiments Plastics in the Ocean: Challenges and Solutions Molly Geidel: Mid-Century Liberalism and the Development Film An approach to the four colour theorem via Donaldson- Floer theory Mathematical applications of little string theory Protein Folding, Evolution and Interactions Symposium Understanding mechanisms and targets of malaria immunity to advance vaccine development Active bacterial suspensions: from individual effort to team work A cabinet of natural history: the long-lost Paston collection |