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
Distributed decision and verification by mobile ag
Algorithmique distribuée
Tuesday 22 January 2019 - 10h30
Salle : 465 - PCRI-N
Evangelos Bampas .............................................

Redundancy in Distributed Proofs
Algorithmique distribuée
Tuesday 04 December 2018 - 00h00
Salle : 465 - PCRI-N
Ami Paz .............................................

Some recent results on the integer linear programm
Théorie des graphes
Friday 30 November 2018 - 00h00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Scalable and exhaustive screening of metabolic fun
Wednesday 28 November 2018 - 11h00
Salle : 465 - PCRI-N
Clémence Frioux .............................................

De la sociologie *avec* des algorithmes à la socio
Friday 09 November 2018 - 14h30
Salle : 445 - PCRI-N
Christpohe Prieur .............................................