===== Today’s 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