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
Analysis of dynamic processes
Load balancing and resource allocation
Scheduling and routing
Publications: please go to DBLP