Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

28 novembre 2016

Robustness against Consistency Models with Atomic Visibility

Bernardi Giovanni (IRIF)

To achieve scalability, modern Internet services often rely on
distributed databases with consistency models for transactions
weaker than serializability.
At present, application programmers often lack techniques to ensure
that the weakness of these consistency models does not violate
application correctness.
In this talk I will present criteria to check whether applications
that rely on a database providing only weak consistency are robust,
i.e., behave as if they used a database providing serializability,
and I will focus on a consistency model called Parallel Snapshot Isolation.
The results I will outline handle systematically and uniformly several
recently proposed weak consistency models, as well as a mechanism for
strengthening consistency in parts of an application.

21 novembre 2016

Un théorème de Dixon pour les groupes d’automates

Thibaud Godin (IRIF)

As every finite group is a subgroup of some permutation group, the most natural idea to generate random finite groups is to pick some random permutations and consider the group they generate. However, Dixon proved that this approach fails, as  it generically leads to generate the symmetric are the alternating group.
Mealy automata, on the other hand, are a powerful tool to generate groups and have been used to solve several important group theoretic conjectures. In particular, any finite group can be generated by a Mealy automaton, hence the idea of doing random generation by drawing random automata.

In this talk we will present this method and prove an analogue to Dixon’s theorem for a certain class of Mealy automata. Then we will discuss how to avoid this convergence of the distribution of generated groups.

14 novembre 2016

An Abstraction Technique For Parameterized Model Checking of Leader Election Protocols

Ocan Sankur (IRISA CNRS)

We consider distributed timed systems that implement leader
election protocols which are at the heart of clock synchronization proto-
cols. We develop abstraction techniques for parameterized model check-
ing of such protocols under arbitrary network topologies, where nodes
have independently evolving clocks. We apply our technique for model
checking the root election part of the flooding time synchronisation pro-
tocol (FTSP), and obtain improved results compared to previous work.
We model check the protocol for all topologies in which the distance to
the node to be elected leader is bounded by a given parameter.

7 novembre 2016

Compositional Strategy Synthesis for Stochastic Games with Multiple Objectives

Nicolas Basset (ULB)

We focus on stochastic games,
which can model interaction with an adverse environment,
as well as probabilistic behaviour arising from uncertainties.
Our contribution is twofold.
First, we study long-run specifications
expressed as quantitative multi-dimensional
mean-payoff and ratio objectives.
We then develop an algorithm to synthesise epsilon-optimal strategies for conjunctions of almost sure satisfaction for mean payoffs
and ratio rewards (in general games) and Boolean combinations of expected
mean-payoffs (in controllable multi-chain games).
Second, we propose a compositional framework, together with assume-guarantee rules,
which enables winning strategies synthesised for individual components to be composed to a winning strategy for the composed game.
The framework applies to a broad class of properties, which also include expected total rewards,
and has been implemented in the software tool PRISM-games.

17 octobre 2016

What’s p-value anyway?

Yuri Gurevich (Microsoft Research)

It seems that all statisticians know the concept of p-value is but none is willing to explain it. The only reference that we have been able to find is the  1974 book « Theoretical Statistics » by Cox and Hinkley where the authors define the concept, sort of, but do not use the term « p-value. »
We explain the concept presupposing only rudimentary probability theory; we examine the concept and we discuss the use of it.
For simplicity, our explanation is focused on the discrete case with no outcomes of zero probability but we’ll say a few words on the general case as well.
The talk builds on joint work with Vladimir Vovk of the University of London.

10 octobre 2016

Lemme de Schoenfield dans les degrés continus

Paul-Elliot Anglès d'Auriac (LACL)

Traditionnelement, la théorie de la calculablilité se fait dans l’espace de Cantor : l’espace des suites infinies de 0 et de 1. Cependant, il est possible de définir ce qu’est un élément calculable, une fonction calculable, dans des espaces plus généraux. Cela nous permet par exemple de définir un calcul prenant en entrée un réél sans passer par sa représentation en binaire.
Un de ces espaces, le cube de Hilbert ([0;1]^N), présente la particularité de posséder des éléments qui ne sont calculatoirement équivalents à aucun élément de l’espace de Cantor. Les degrés du cube de Hilbert sont appelés degrés continus.
Dans cette exposé nous allons voir comment un théorème de calculabilité classique s’étend aux degrés continus : le lemme de Schoenfield, qui affirme que X est calculable en le problème de l’arret si et seulement si on peut calculer une suite qui converge vers X.

3 octobre 2016

Décalage multiplicatif et dimensions

Lingmin Liao (LAMA - UPEC)

Considérons l’ensemble des suites de 0 et 1. Nous nous intéressons au sous-ensemble des suites dont les chiffres à la position k et à la position 2k ne sont pas deux 1 pour chaque k. On l’appelle le décalage de Fibonacci multiplicatif. C’est un analogue du décalage de Fibonacci classique qui est l’ensemble des suites qui ne contiennent pas deux 1 consécutifs. Le décalage de Fibonacci multiplicatif a la mesure de Lebesgue zéro. Pour trouver sa « vraie taille », nous calculons ses dimensions fractales : dimensions de Minkowski et de Hausdorff. Les deux dimensions sont différentes : la première est donnée par une série numérique concernant la suite de Fibonacci et la seconde est une solution d’une équation algébrique.

19 septembre 2016

Calculabilité de l’entropie des pavages mélangeants

Benjamin Hellouin (IRIF)

L’entropie topologique d’un système dynamique est un paramètre réel qui mesure sa complexité dynamique. J’étudie ici deux questions liées: quelle valeur peut prendre ce paramètre, et peut-on le calculer (algorithmiquement) ?

Dans les sous-shifts ou pavages de type fini (SFT) en dimension 1, on sait la calculer depuis 30 ans, et la méthode utilisée nous permet de caractériser l’ensemble des entropies possibles par une condition algébrique. En dimension supérieure, la surprise est venue en 2007 : non seulement l’entropie n’est pas calculable, mais l’ensemble des réels semi-calculables par le haut apparaissent comme entropies possibles. C’est le premier d’une série de résultats de « réalisation » qui s’est depuis décliné sur de nombreux autres objets.

Sous des hypothèses supplémentaires, par exemple de fortes conditions de mélange, l’entropie redevient calculable; les entropies possibles sont alors caractérisées par des conditions de calculabilité plus fortes. Les hypothèses « minimales » de ce résultat ne sont pas encore bien comprises.

Dans cet exposé, j’explore le cas des sous-shifts ou pavages généraux, i.e. pas de type fini. Je met en relation la difficulté de décider si un motif apparait dans le pavage et la difficulté de calculer la valeur de l’entropie. J’exhibe un saut de difficulté qui est fonction du taux de mélange, le problème devenant brusquement plus difficile au-delà d’une valeur seuil.

Ce travail est une collaboration avec Silvère Gangloff, Mathieu Sablik et Cristobal Rojas.

12 septembre 2016

Le genre asymptotique d’un jeu de tuiles

Thierry Monteil (LIPN)

Un jeu de tuiles de Wang est un ensemble fini de carrés unités dont
on a colorié chaque côté. Un jeu de tuiles T pave le plan si celui-ci peut
être recouvert par des translatés de copies d'éléments de T (selon Z^2), de
sorte que les arêtes en contact de deux tuiles adjacentes soient de même
couleur. Un jeu de tuiles est dit apériodique s'il pave le plan mais si
aucun pavage obtenu n'est invariant par une translation. La plupart des jeux
de tuiles apériodiques sont construits de façon autosimilaire (via une règle
de substitution).

Nous avons introduit deux invariants permettant de quantifier le niveau
d'apériodicité d'un jeu de tuiles de Wang. L'un des invariants est de nature
topologique, l'autre est métrique. Nous nous attarderons sur le premier, qui
consiste a paver de grandes surfaces (dites "de translation") tout en
minimisant leur genre.