Janvier 2022 — Algorithmique et Structures Discrètes

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.

Novembre 2021 — Géométrie et Topologie du Calcul

Cette demi-journée pôle calcul aura lieu le 18 novembre. Nous aurons la chance d’avoir trois orateurs.

Orateur : Dmitry Sokolov (LORIA)
Titre : How to compute locally invertible maps
Résumé : Mapping a triangulated surface to 2D plane (or a tetrahedral mesh to 3D space) is the most fundamental problem in geometry processing. The critical property of a good map is a (local) invertibility, and it is not an easy one to obtain. We propose a mapping method inspired by the mesh untangling problem. In computational physics, untangling plays an important role in mesh generation: it takes a mesh as an input, and moves the vertices to get rid of foldovers. In fact, mesh untangling can be considered as a special case of mapping, where the geometry of the object is to be defined in the map space and the geometric domain is not explicit, supposing that each element is regular. This approach allows us to produce locally invertible maps, which is the major challenge of mapping. In practice, our method succeeds in very difficult settings, and with less distortion than the previous work, both in 2D and 3D.

Orateur : Corentin Travers (LABRI)
Titre : Synchronous t-Resilient Consensus in Arbitrary Graphs
Résumé : We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.

Our lower bound technique is inspired by the topological techniques for distributed computing. It is similar to the connectivity analysis of the protocol complex, the structure of states at the end of executions of an algorithm after a certain number of rounds. However, instead of working with the protocol complex, we consider an information flow directed graph version based on failure patterns.

Joint work with Armando Castaneda, Pierre Fraigniaud, Ami Paz, Sergio
Rajsbaum, and Matthieu Roy

Orateur : Victor Chepoi (LIS)
Titre : 1-safe Petri nets and special cube complexes
Résumé : In the talk, I will explain the following bijection between 1-safe Petri nets and finite special cube complexes: the event structures arising as unfolding of 1-safe Petri nets are exactly the event structures whose domains arise as principal filters of the universal cover of a finite 1-safe Petri net.

This can be viewed as a positive answer to the (disproved) conjecture by Thiagarajan that the event structures arising as unfolding of 1-safe Petri nets are exactly the regular event structures. If the time permits, I will give some (positive and negative) applications of this bijection.

Joint work with Jérémie Chalopin.

Octobre 2021 — Logique et méthodes formelles

Le 14 octobre à la FRUMAM – de 9h30 à 12h30.

Orateur : Ugo Dal Lago (UniBo)
Titre : On Higher-Order Cryptography
Résumé : Type-two constructions abound in cryptography: adversaries for encryption and authentication schemes, if active, are modeled as algorithms having access to oracles, i.e. as second-order algorithms. But how about making cryptographic schemes higher-order themselves? Moreover, how about seeing cryptographic reductions as higher-order functions? We give an answer to this question, by first describing why higher-order cryptography is interesting as an object of study, and then showing how the concept of probabilistic polynomial time algorithm can be generalised so as to encompass algorithms of order strictly higher than two. We then prove some positive and negative results about the existence of higher-order cryptographic primitives, namely authentication schemes and pseudorandom functions. The talk is based on some joint work with Boaz Barak and Raphaëlle Crubillé.

Orateur : Pierre Clairambault (LIS)
Titre : Games with no Winner: an Introduction to Game Semantics
Résumé : How to define rigorously the behaviour of programs under execution?
Program semantics is a necessary first step in order to prove that a program or program transformation is correct, and is of course a preliminary to any theoretical question on programming languages. Game semantics is one of many approaches to program semantics. It represents a program by recording the exchange of observable computational events with its execution environment, phrased as a play in a two-player game that the program plays with its context. In game semantics there is no winner: it is about the journey, not the destination!

Most of my talk will be an introduction to game semantics. I will first focus on some old (but nice) results, namely the so-called « semantic cube » following which game semantics exactly captures the observable behaviour of programs with various computational effects (notably, mutable state and non-local control). I will show how this allows one to prove results about computational effects and their interferences.

Time permitting, I will then talk about some of my own recent work on a game semantics for concurrent programs. The semantics builds on so-called « true concurrency » models such as event structures, and provides a causal description of the behaviour of concurrent programs with rich computational features.

Orateur : Raphaelle Crubillé (LORIA)
Titre : Sémantique dénotationelle pour les languages de programmation probabilistes
Résumé : La sémantique dénotationelle est un champs de recherche centré sur la construction de modèles mathématiques des languages de programmation, visant à produire des techniques de preuve pour l’équivalence de programmes. Dans les dix dernières années, l’usage des probabilités pour la programmation a été transformé par les dévelopements en programmation statistique et en apprentissage, ce qui a stimulé un intérêt renouvelé pour les méthodes formelles pour des languages probabilistes. Cet exposé présente un bref panorama de la sémantique dénotationelle des langages de programmation probabilistes, en tentant d’expliciter à la fois ses enjeux, ses outils et ses perspectives.