Séminaire des doctorants

Séminaire dans lequel les doctorant.e.s et les stagiaires présentent leur travaux devant une audience moins intimidante puisqu'elle est composée des autres doctorant.e.s, stagiaires et éventuellement post-docs.

Date et lieu : le mercredi à 11h, Sophie Germain

Responsables : Laurent Feuilloley, Nicolas Jeannerod, Théo Zimmermann

Mercredi 08 mars 2017 · 11h00 · Salle 3052

Pablo Eduardo Rotondo (Automata and applications Group) · TBA

Mercredi 22 mars 2017 · 11h00 · Salle 3052

Gabriel Radanne (PPS team) · TBA

Mercredi 05 avril 2017 · 11h00 · Salle 3052

Guillaume Lagarde (Automata and applications Group) · TBA

Mercredi 22 février 2017 · 11h00 · Salle 3052

Lucas Boczkowski (Algorithms and complexity Group) · Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

The talk is based on a paper whose abstract is the following:

This paper considers the basic PULL model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of n agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast (also termed Rumor Spreading). We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. In particular, the specification of who is a source and what is its initial input bit may be set by an adversary.

We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property (called “the bitwise-independence property”) that uses l-bits messages to one that uses only (log l)-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer T, within O(log n log T) rounds w.h.p., and using messages that contain 3 bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing majority broadcast protocol which converges in O(log n) time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.

Based on joint work with A. Korman and E. Natale.

Mercredi 25 janvier 2017 · 11h00 · Salle 3052

Thibaut Girka (PPS team) · Oracle-based Differential Operational Semantics (or Explaining program differences with programs)

We present a formal framework to characterize differences between deterministic programs in terms of their small-step semantics. This language-agnostic framework defines the notion of /difference languages/ in which /oracles/—programs that relate small-step executions of pairs of programs written in a same language—can be written, reasonned about and composed.

We illustrate this framework by instantiating it on a toy imperative language and by presenting several /difference languages/ ranging from trivial equivalence-preserving syntactic transformations to characterized semantic differences. Through those examples, we will present the basis of our framework, show how to use it to relate syntactic changes with their effect on semantics, how one can abstract away from the small-step semantics presentation, and discuss the composability of oracles.

Mercredi 11 janvier 2017 · 11h00 · Salle 3052

Fabian Reiter (Automata and applications Group) · Asynchronous Distributed Automata

The goal of this talk is to raise interest in the connections between distributed computing and formal logic. I will illustrate this relatively unexplored area of research by presenting an equivalence result between two very specific systems. The distributed computing side will be represented by a network of identical finite-state machines that communicate in an asynchronous manner, while the formal logic side will be represented by a small fragment of least fixpoint logic (more specifically, a fragment of the modal mu-calculus).

Voir les archives sur l'ancien site web : http://www.pps.univ-paris-diderot.fr/~c.jacq/seminaire-thesards