[talks] Today's Department Colloquium at 4:30 pm Sherrerd Hall 101: Yuval Peres, Microsoft

[Emily Lawrence]

===== 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<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.

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20180925/bd32fd8a/attachment.html>