BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Consensus -- with Limited Memory and Signalling - Milan Vojnovic\,
  Microsoft research Cambridge
DTSTART:20081016T150000Z
DTEND:20081016T160000Z
UID:TALK14159@talks.cam.ac.uk
CONTACT:Neil Walton
DESCRIPTION:We consider the binary consensus problem where each node in th
 e 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.\, c
 omplete graphs). It is well known that for systems with binary signalling 
 and memory\, the probability of reaching incorrect consensus is equal to t
 he fraction of nodes that initially held the minority state. We show that 
 extending both the signalling and memory by just one state dramatically im
 proves the reliability and speed of reaching the correct consensus. Specif
 ically\, we show that the probability of error decays exponentially with t
 he number of nodes N and the convergence time is logarithmic in N for larg
 e 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 l
 ogarithmic in N for large N\, and is therefore faster than purely binary s
 ystems. 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 efficie
 nt protocols can be built with rather limited signalling and memory.
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR