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
Quantum at LRI
Calcul quantique
Tuesday 04 February 2020 - 09h00
Salle : 465 - PCRI-N
.............................................

Progressive Data Analysis: a new computation parad
Gestion de données du Web
Friday 24 January 2020 - 14h00
Salle : 435 - PCRI-N
Jean-Daniel Fekete .............................................

Jeux d’instructions : des extensions SIMD aux exte
Architectures parallèles
Tuesday 21 January 2020 - 10h30
Salle : 465 - PCRI-N
Daniel Etiemble .............................................

Forum dev-LRI
Tuesday 14 January 2020 - 14h00
Salle : 445 - PCRI-N
Erik Bray .............................................

La transformation du travail, un analyseur des tra
Wednesday 18 December 2019 - 10h00
Salle : 475 - PCRI-N
Raquel Becerril-Ortega .............................................