Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
Approximate Consensus in Highly Dynamic Networks
Bernadette Charron-Bost

10 April 2015, 10h00 - 10 April 2015, 15h30
Salle/Bat : 475/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 syn- chronous and partially synchronous networks, approximate consensus is solvable if and only if permanently, the communication graph has a rooted spanning tree. The striking point is that the spanning tree may continually change over time without preventing nodes from converging to consensus. Actually 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.
We develop a proof strategy which consists in a reduction to the nonsplit networks. It dramatically improves the best known upper bound on the decision times of averaging algo- rithms and yields a non-averaging algorithm for approximate consensus in non-anonymous networks with a decision time that is quadratic in the number of nodes. We also prove that a general upper bound on the decision times of averaging algorithms has to be exponential, shedding light on the high price of anonymity.
Finally we apply our results to networked systems with a fixed topology and benign fault models to show that with n processes, up to 2n − 3 of link faults per round can be tolerated for approximate consensus, increasing by a factor 2 the tight bound for exact consensus established by Santoro and Widmayer.

Pour en savoir plus :
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 .............................................