Room 206 (2nd floor, badged access)
6 February 2020 - 14h00
Lower bounds for probabilistic k-set agreement through combinatorial topology
by Jules Chouquet from IRIF
Abstract: Herlihy and Shavit (1999) introduced a powerful method for the analysis of distributed algorithms (in a shared memory with immediate snapshot model) that uses topological properties of simplicial complexes. This methods allows to prove impossibility results of some problems in distributed computing, like consensus, or k-set agreement (which is a generalization of consensus).
Beyond the impossibility, it is known that those problems admit protocols that solve them if non determinism is allowed. We show how Herlihy and Shavit topological methods can be used to infer lower bounds for those probabilistic algorithms (k-set agreement, and consensus as the particular situation where k=1), giving a formal account to the intuition that the probability of success increases with the number of rounds.
