We study consensus processes on the complete graph of n nodes. Initially, each node supports one up to n different opinions. Nodes randomly and in parallel sample the opinions of constantly 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 (say n1/3), 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. In particular, we show that 3-Majority reaches consensus with high probability in O(n3/4 · log7/8 n) rounds, while 2-Choices can need Ω(n / log n) rounds. We thus 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.
Berenbrink, P., Clementi, A., Elsasser, R., Kling, P., Mallmann-Trenn, F., & Natale, E. (2017). Ignore or comply? On breaking symmetry in consensus. In Proceedings of the 36th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2017) (pp.335-344). ACM [10.1145/3087801.3087817].
|Autori:||Berenbrink, P; Clementi, A; Elsasser, R; Kling, P; Mallmann-Trenn, F; Natale, E|
|Titolo:||Ignore or comply? On breaking symmetry in consensus|
|Nome del convegno:||ACM Symposium on Principles of Distributed Computing (PODC 2017)|
|Luogo del convegno:||Washington, DC, USA|
|Anno del convegno:||2017|
|Enti collegati al convegno:||ACM|
|Data di pubblicazione:||25-lug-2017|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1145/3087801.3087817|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni
|Tipologia:||Intervento a convegno|
|Citazione:||Berenbrink, P., Clementi, A., Elsasser, R., Kling, P., Mallmann-Trenn, F., & Natale, E. (2017). Ignore or comply? On breaking symmetry in consensus. In Proceedings of the 36th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2017) (pp.335-344). ACM [10.1145/3087801.3087817].|
|Appare nelle tipologie:||02 - Intervento a convegno|