Event Information

Title: CS Colloquium: Petra Berenbrink, School of Computing Science, Simon Fraser University and Universitšt Hamburg
Sharing: Public
Start Time: Friday April 19, 2019 03:00 PM
End Time: Friday April 19, 2019 04:00 PM
Location: Luddy Hall
Contact: Funda Ergun
Url: https://www.inf.uni-hamburg.de/inst/ab/art/people/berenbrink.html
Free/Busy: busy

The School of Informatics, Computing, and Engineering (SICE) CS Colloquium Series

Speaker:   Petra Berenbrink, School of Computing Science, Simon Fraser University & Universität Hamburg 

Where:  Luddy Hall, Rm. 1106 (Dorsey Learning Hall)

When:  April 19, 2019, 3:00 pm

Topic:  Ignore or Comply? On Breaking the Symmetrie in Consensus

Abstract:  We study consensus processes on the complete graph of n nodes. Initially, each node supports one from up to n opinions. Nodes randomly and in parallel sample the opinions of constant many nodes. Based on these samples, they use an update rule to change their own opinion. 

The goal is to reach consensus, a configuration where all nodes support the same opinion. We compare two well-known update rules: 2-Choices and 3-Majority. In the former, each node samples two nodes and adopts their opinion if they agree. In the latter, each node samples three nodes: If an opinion is supported by at least two samples the node adopts it, otherwise it randomly adopts one of the sampled opinions. Known results for these update rules focus on initial configurations with a limited number of colors, or typically assume a bias, where one opinion has a much larger support than any other. For such biased configurations, the time to reach consensus is roughly the same for 2-Choices and 3-Majority. 

Interestingly, we prove that this is no longer true for configurations with a large number of initial colors. We get the first unconditional sublinear bound for 3-Majority and the first result separating the consensus time of these processes. Along the way, we develop a framework that allows a fine-grained comparison between consensus processes from a specific class. We believe that this framework might help to classify the performance of more consensus processes.

Joint work with Andrea Clementi, Robert Elsaesser, Peter Kling, Frederik Mallmann-Trenn and Emanuele Natale



  • Probabilistic methods
  • Randomised algorithms
  • Analysis of dynamic processes
  • Game theory
  • Load balancing and resource allocation
  • Scheduling and routing

Publications: please go to DBLP


Contact Email: fergun@indiana.edu
Share this Event:
I'm going copy to my calendar back