===== Todays ORFE Department Colloquium Announcement=====
DATE: Tuesday, September 25th, 2018
TIME: 4:30pm
LOCATION: Sherrerd Hall 101
SPEAKER: Yuval Peres, Microsoft Research
Title: Communication cost of consensus for nodes with limited
memory
Abstract: Motivated by applications in blockchain and sensor networks,
we consider a model of n nodes trying to reach consensus on their majority
bit (which a fraction p>1/2 of them possess; the rest start with the
minority bit). Each node v is a finite automaton with m bits of memory
(i.e., 2^m states), and a Poisson clock. When it rings, the node v can
choose to communicate, and is then matched to a uniformly chosen node u,
whence both v,u can update their states based on the other nodes state.
Previous work has focused on minimizing the time to consensus and the
probability of error; our goal is minimizing communication. We show that
when m>3 logloglog(n), consensus can be reached at linear communication
cost, but this is impossible if m