Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) ParSys
Time-Optimal Approximate Consensus in Highly Dynamic Networks
Thomas Nowak

17 November 2015, 10h30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Algorithmique distribuée

Résumé :
We investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both synchronous and partially synchronous networks, approximate consensus is solvable if and only if the communication graph in each round has a rooted spanning tree. Interestingly, the class of averaging algorithms, which have the benefit of being memoryless and requiring no process identifiers, entirely captures the solvability issue of approximate consensus in that the problem is solvable if and only if it can be solved using any averaging algorithm.

After this characterization of solvability of approximate consensus, we turn to the question of time complexity. We give an algorithm that solves approximate consensus in time linear in the numer of nodes in the network and show the optimality of its time complexity up to a multiplicative constant. We also present its generalization to higher dimensional values and the case of finite memory, in which rounding procedures will be necessary.

This is joint work with Bernadette Charron-Bost and Matthias Függer.

Pour en savoir plus : https://parsys.lri.fr/seminar.html
Séminaires
Demographic reconstruction from paleogenomes of th
Thursday 25 February 2021 - 14h00
Salle : 435 - PCRI-N
Nina Marchi .............................................

A Graph-based Similarity Approach to Classify Recu
Thursday 18 February 2021 - 14h00
Salle : 435 - PCRI-N
Coline Gianfrotta .............................................

"Answer Set Programming for computing constraints-
Thursday 04 February 2021 - 14h00
Salle : 435 - PCRI-N
Maxime Mahout .............................................

"Pandæsim: An Epidemic Spreading Stochastic Simula
Thursday 14 January 2021 - 14h00
Salle : 435 - PCRI-N
Patrick Amar .............................................

Disentangling the role of selection on the evoluti
Friday 02 October 2020 - 17h30
Salle : 455 - PCRI-N
Fanny Pouyet .............................................