Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it will return a normal behavior in finite time. Several constraints concern algorithms designed for distributed systems. Asynchrony is one emblematic example. With the development of networks of connected, autonomous devices, it also becomes crucial to design algorithms with a low energy consumption, and not requiring much in terms of resources.

One way to address these problems is to aim at reducing the size of the messages exchanged between the nodes of the network. This thesis focuses on the memory optimization of the communication for self-stabilizing distributed algorithms. We will present a negative results, proving the impossibility to solve some problems under a certain limit on the size of the exchanged messages, and a particularly efficient algorithms in terms of memory for one fundamental problem in distributed systems: the token circulation.

Reaching consensus in a distributed system is one of the most fundamental problems studied in distributed computing. It is non-trivial due to uncertainties related to unsuccessful communication and process faults. In particular, the celebrated FLP impossibility result shows why scheduling an event via an asynchronous communication medium such as email is difficult. In this talk, I will present our recent results on exact and approximate consensus in hostile environments such as dynamic networks (e.g., due to mobility of agents) and synthetic bacterial cultures

We discuss the formalization of Linear Logic, through the development of the Yalla library for Coq:

https://perso.ens-lyon.fr/olivier.laurent/yalla/

The initial specification was to get a library which:

• would provide standard results on the proof theory of Linear Logic;
• could be reused, thus in particular able to deal with some variants of the system;
• should be compatible with the Curry-Howard interpretation of proofs, thus faithful to their computational content.

We will describe the evolution of the project and how it matches this specification through the different versions of the library: Yalla 1, Yalla 2 (current version), Yalla 3 (future directions).

Following all previous known works, Yalla 1 defined proofs in Prop. It relies on an explicit exchange rule for dealing with the computational content of proofs. Yalla 2 corresponds to a move to Type to be able to extract computational informations from proofs. Yalla 3 will rely on a different way of approaching exchange to be able to deal with local transformations of proofs more easily.

Box-totally dual integral polyhedra are polyhedra hidden behind strong min-max relations, such as the MaxFlow-MinCut Theorem of Ford and Fulkerson. Box-perfect graphs are the perfect graphs whose stable set polytope is box-totally dual integral, and the question of their characterization, raised is 1982 by Cameron and Edmonds, is still open.

In this talk, we will survey recent characterizations of box-totally dual integral polyhedra, and discuss some consequences for box-perfect graphs. This is based on joint works with P. Chervet and L.-H. Robert.

In the context of large-scale networks, fault tolerance is a necessity. Self-stabilization is an algorithmic approach to fault tolerance in distributed systems. Its aim is to manage processors' memory corruption due to transient failures. The efficiency of a self-stabilizing algorithm is characterized by several parameters, including (1) the time taken by the system to return to a legal configuration after an arbitrary corruption of its processors' memory, and (2) the memory space used by the processors to execute the algorithm. Minimizing memory space is motivated by many aspects, such as networks (e.g. sensor networks) with limited memory space, minimizing data exchanges between processors, and limiting information storage to use redundancy techniques. This seminar will present self-stabilization through two main classical problems: constructing spanning trees, especially those of minimum weight, and electing a leader. It will cover the links between self-stabilization and distributed decision techniques, including computing lower bounds on memory space needed to solve the aforementioned problems using self-stabilizing algorithms.

We consider the traditional goals of cryptography, including secure communication and secure computation, when allowing only one-way communication over noisy channels: - Can Alice transmit a message to Bob without Eve learning this message? - Can Alice transmit exactly one of two messages to Bob without Alice learning which message was received?

We show how to circumvent information-theoretic impossibility results by settling for computational security and using the power of cryptographic obfuscation. In particular, under plausible assumptions, we obtain a positive answer to the first question whenever Alice's channel to Bob is not a degradation of the channel to Eve, and a positive answer to the second question over simple channels such as a binary symmetric channel or a binary erasure channel.

The first part of the talk is based on joint work with Alexis Korb, Paul Lou, and Amit Sahai. The second part is based on joint work with Shweta Agrawal, Eyal Kushilevitz, Varun Narayanan, Manoj Prabhakaran, Vinod M. Prabhakaran, and Alon Rosen.

In this talk, we will introduce a space constrained model of computation, aka the Streaming Model. In particular, we will look at a simple algorithm for degeneracy based graph coloring in this model, which was proposed in 2019 and is currently the state of the art (in terms of number of colors used). We will complement the algorithm with a corresponding lower bound which uses a reduction to the problem of indexing in communication complexity and end with an open problem.

No prerequisite is assumed and every notion used will defined in the talk.

This presentation is based on the paper “Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models” by Suman Kalyan Bera, Amit Chakrabarti and Prantar Ghosh.

This talk is about winning strategies in Markov decision processes and stochastic games and is aimed at a general computer science audience. We start by recalling some of the basic notions in game theory, such as values, strategies, and the memory requirements of optimal and ε-optimal strategies. We will describe a set of recent advances on strategy complexity of verification-centered objectives, such as subclasses of parity objectives, in terms of parameters such as the cardinality of the state space, branching factor of the transition function, and whether the game is concurrent or turn-based.

https://semflajolet.math.cnrs.fr/