Évènements

December 2018
14 December 2018

Séminaire DALGO: Thomas Nowak (LRI), vendredi 14 à 10h30

Title: Approximate Agreement in Dynamic Networks Abstract: Agreeing on a common value in a distributed system is a problem that lies at the heart of many distributed computing problems and occurs in several flavors. Unfortunately, even modest network dynamics already prohibit solvability of exact consensus, where agents have to decide on a single output value that is within the range of the agents' initial values. For many problems (distributed control, clock synchronization, load balancing, ...) it is however sufficient to asymptotically converge to the same value, or decide on values not too far from each other. We study solvability of these consensus variants in highly dynamic networks, provide time complexity results, and present fast algorithms. We then show how the results on dynamic networks are relevant for classical fault-models, such as asynchronous message passing with crashes. The talk is based on joint work with Bernadette Charron-Bost, Matthias Függer, and Manfred Schwarz.

20 December 2018

Séminaire CaNa : 20 décembre à 14h : SAT est NP-complet, la preuve !

Résumé : Ne croyez pas ce que l'on vous a dit, le théorème de Cook-Levin n'est pas si difficile que cela à démontrer... J'ai longtemps admis cette preuve, et après l'avoir lue dans le livre de Sylvain Perifel, j'ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-)

January 2019
Tutelles