Cette demi-journée aura lieu le 20 janvier sur zoom.
Orateur : Alessia Milani (LIS)
Titre : Concurrent Counters with Polylogarithmic Step Complexity
Résumé : Shared data objects are an essential abstraction in distributed computing, as they provide a consistent interface for multiple processes to interact via shared data. Linearizability is the main consistency criterion that formalizes the correctness of shared object implementations. Linearizable shared objects are intuitive to use, but they can be expensive to implement.
In this talk, I will consider a widely-used shared object, the counter. I will present a fundamental lower bound on the worst-case complexity of fault-tolerant implementations of counters and two ways of circumventing it. In particular, in 2000, Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of shared objects, including counters. In 2012, Aspnes, Attiya and Censor-Hillel observed that the lower bound holds only when numerous operations are applied to the object and does not rule out the possibility of obtaining algorithms whose step complexity is sub-linear when the number of operations is bounded.
We recently prove that there exists deterministic counters implementations with sub-linear amortized step complexity regardless of how many operations are performed on the object. This is a joint work with Mirza Ahad Baig, Danny Hendler and Corentin Travers
The talk will be self-contained.
Orateur : Eloi Perdereau (LIS)
Titre : Accords Approchés et Asymptotiques pour les Adversaires de Message
Résumé : En calculabilité des systèmes distribués, les problèmes du Conensus et de l’Accord k-Ensembliste sont beaucoup étudiés car permettent de mettre en valeur des aspects fondamentaux des modèles. L’objet de notre travail est de proposer et d’étudier des relaxations du problème de l’Accord k-Ensembliste, sous l’angle de l’approximation géométrique de valeurs, à l’instar du Consensus Approché. Nous proposons deux nouveaux problèmes : l’Accord k-Convexe Approché et l’Accord k-Convexe Asymptotique, et étudions leur calculabilité pour des algorithmes de moyennes.
Le modèle distribué est celui des adversaires de message qui se base sur des séquences de graĥes dynamiques définissant les exécutions. Les scénarios considérés sont clos par suffixes et ont des comportements de récurrence bornée soit par l’apparition des arcs (BRec et FRec), soit par l’influence de certains sommets sur les autres (BISC et FISC). Ces adversaires forment une hiérarchie de fait et nous allons montrer que ces deux problèmes permettent de les séparer du point de vue de la calculabilité distribuée.