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<logloglog(n). The best algorithms we know intrinsically select a set of “expert” nodes that learn the majority bit, and then disseminate this knowledge. A key step is to distinguish when nodes can become “aware” of reaching the majority bit and stop communicating; this is impossible if their memory is too low. (Joint work with Giulia Fanti, Nina Holden and Gireeja Ranade).

Biography: Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. He obtained his Ph.D. at the Hebrew University, Jerusalem in 1990, and later taught there and at the University of California, Berkeley. He has published more than 300 research papers and has co-authored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995, the Loève Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Math. and in the 2008 European Congress, and was a plenary lecturer at the Math. Congress of the Americas in 2017. He has advised 22 Ph.D. students. He is a fellow of the American Math. Society and the Institute of Mathematical Statistics. In 2016 he was elected to the U.S. National Academy of Sciences.