Logo IRISA      logo Inria

Le séminaire en bref

Le séminaire 68NQRT est un séminaire commun de l'IRISA et d'Inria Rennes. Il a lieu le jeudi à 14 heures par défaut dans la salle Markov. Les thèmes du séminaire recouvrent des thèmes étudiés dans les départements « réseaux, télécommunication et services » et « langage et génie logiciel » de l'IRISA, ou des thèmes « Algorithmique, programmation, logiciels et architectures » et  « Réseaux, systèmes et services, calcul distribué » d'Inria. On y trouve des exposés introductifs, avancés ou prospectifs dans les thèmes du génie logiciel, de l'informatique théorique, des mathématiques discrètes et de l'intelligence artificielle.

D'après Mathematical Subject Classification:
68 Computer Science
N Software
Q Theory of computing
R Discrete mathematics in relation to computer science
T Artificial intelligence

Prochain Exposé

vendredi 23 septembre, 11h en salle Minquiers

Bernadette Charron-Bost (Ecole polytechnique)

Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms

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. We develop a proof strategy which for each positive result consists in a reduction to the non-split networks. It dramatically improves the best known upper bound on the decision times of averaging algorithms. We also prove that a general upper bound on the decision times of averaging algorithms have to be exponential, shedding light on the price of memoryless algorithms. 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 bound of Santoro and Widmayer for exact consensus.

Exposés des semaines suivantes

jeudi 27 Octobre 14h

Béatrice Bérard

Preserving opacity on Interval Markov Chains under simulation.

To Be Anounced

jeudi 17 novembre, 14h

Thomas Chatain (LSV)

Anti-alignments in Conformance Checking - The Dark Side of Process Models

To Be Anounced