Search

International audience; La M-exclusion a pour but de partager L ressources identiques. Elle est définie par trois propriétés : l'équité, la sûreté et une propriété d'efficacité appelée évitement de L-interblocage. Nous montrons que tout algorithme réalisant ces trois propriétés a un temps d'attente en Omega(n-L) rondes dans un anneau de n processus. Donc, quand n est grand comparé à L, le gain d'avoir L ressources identiques au lieu d'une seule devient négligeable. Pour contourner ce problème, nous reformulons la définition de L-exclusion en remplaçant la propriété d'évitement de L-interblocage par une contrainte sur le temps d'attente. Nous illustrons cette nouvelle version du problème avec des algorithmes autostabilisants dont le temps d'attente est en O(n/L) rondes, la borne asymptotique optimale.

Given two functions f and g mapping nodes to non-negative integers, we give a silent self-stabilizing algorithm that computes a minimal ( f , g ) -alliance in an asynchronous network with unique node IDs, assuming that every node p has a degree at least g ( p ) and satisfies f ( p ) ? g ( p ) . Our algorithm is safely converging in the sense that starting from any configuration, it first converges to a (not necessarily minimal) ( f , g ) -alliance in at most four rounds, and then continues to converge to a minimal one in at most 5 n + 4 additional rounds, where n is the size of the network. Our algorithm is written in the shared memory model. It is proven assuming an unfair (distributed) daemon. Its memory requirement is ? ( log n ) bits per process, and it takes O ( n ? Δ 3 ) steps to stabilize, where Δ is the degree of the network. We give an algorithm for the ( f , g ) -alliance, a generalization of several problems.Our algorithm is distributed, self-stabilizing, silent, and safe converging.The complexity analysis shows that it is better than many other related solutions.

Real-time critical systems can be considered as correct if they compute both right and fast enough. Functionality aspects (computing right) can be addressed using high level design methods, such as the synchronous approach that provides languages, compilers and verification tools. Real-time aspects (computing fast enough) can be addressed with static timing analysis, that aims at discovering safe bounds on the worst-case execution time (WCET) of the binary code. In this paper, we aim at improving the estimated WCET in the case where the binary code comes from a high-level synchronous design. The key idea is that some high-level functional properties may imply that some execution paths of the binary code are actually infeasible, and thus, can be removed from the worst-case candidates. In order to automatize the method, we show (1) how to trace semantic information between the high-level design and the executable code, (2) how to use a model-checker to prove infeasibility of some execution paths, and (3) how to integrate such infeasibility information into an existing timing analysis framework. Based on a realistic example, we show that there is a large possible improvement for a reasonable computation time overhead.

We consider the (deterministic) e-exclusion problem, a generalization of the mutual exclusion problem which allows use of 1 ≤ e

International audience; Nous proposons un algorithme distribué, autostabilisant et silencieux avec convergence sûre qui calcule une \fga minimale dans un réseau asynchrone identifié, où $f$ et $g$ sont deux fonctions associant à chaque n\oe ud un entier positif ou nul qui vérifient~: pour tout n\oe ud $p$, $f(p) \geq g(p)$ et $\delta_p \geq g(p)$, où $\delta_p$ est le degré du n\oe ud $p$ dans le réseau.

Given two functions f and g mapping nodes to non-negative integers, we give a silent self-stabilizing algorithm that computes a minimal (f, g)-alliance in an asynchronous network with unique node IDs, assuming that every node p has a degree at least g(p) and satisfies f(p) ≤ g(p). Our algorithm is safely converging in the sense that starting from any configuration, it first converges to a (not necessarily minimal) (f, g)-alliance in at most four rounds, and then continues to converge to a minimal one in at most 5n + 4 additional rounds, where n is the size of the network. Our algorithm is written in the shared memory model. It is proven assuming an unfair (distributed) daemon. Its memory requirement is O(log n) bits per process, and it takes $O(\varDelta^3n)$ steps to stabilize, where $\varDelta$ is the degree of the network.

International audience; In this paper, we address the deterministic rendezvous in graphs where k mobile agents, disseminated at different times and different nodes, have to meet in finite time at the same node. The mobile agents are autonomous, oblivious, labeled, and move asynchronously. Moreover, we consider an undirected anonymous connected graph. For this problem, we exhibit some asymptotical time and space lower bounds as well as some necessary conditions. We also propose an algorithm that is asymptotically optimal in both space and round complexities.

International audience; In this paper, we address the deterministic rendezvous of mobile agents into any unoriented connected graph. The agents are autonomous, oblivious, move asynchronously. For this problem, we exhibit some time and space lower bounds as well as some necessary conditions. We also propose an algorithm that is space-optimal and asymptotically optimal in rounds.

National audience; Ce livre d’exercices corrigés est destiné aussi bien aux étudiants de premier cycle en informatique qu’aux enseignants intéressés par la programmation fonctionnelle. L’ouvrage aborde notamment les notions de correction, de complexité et d’efficacité d’un algorithme fonctionnel, à travers les solutions détaillées d’une quarantaine ’exercices. Pour chacun de ces exercices, plusieurs solutions sont systématiquement proposées. Pour chaque solution, une analyse des temps de calcul et une preuve de correction sont entièrement rédigées. Les exercices traités sont classés en plusieurs catégories en fonction de la nature des données qu’ils manipulent : entiers, listes, arborescences. Cette distinction permet de mettre en avant un mode de programmation et de raisonnement guidé par la structure des données, si naturel en programmation fonctionnelle. Si les exercices proposés peuvent sembler simples et classiques au premier abord, ils ont été choisis pour permettre, par l’étude de leurs solutions, une découverte en profondeur de la programmation fonctionnelle, ce qui constitue l’originalité du livre.

National audience; Dans cet article, nous présentons un algorithme déterministe de rendez-vous pour des agents évoluant dans un graphe non orienté anonyme quelconque. Les agents considérés sont autonomes, amnésiques et se déplacent de manière asynchrone. L'algorithme proposé est optimal en espace et asymptotiquement optimal en nombre de rondes.

This thesis deals with the self-stabilizing construction of spanning structures over a distributed system. Self-stabilization is a paradigm for fault-tolerance in distributed algorithms. It guarantees that the system eventually satisfies its specification after transient faults hit the system. Our model of distributed system assumes locally shared memories for communicating, unique identifiers for symmetry-breaking, and distributed daemon for execution scheduling, that is, the weakest proper daemon. More generally, we aim for the weakest possible assumptions, such as arbitrary topologies, in order to propose the most versatile constructions of distributed spanning structures. We present four original self-stabilizing algorithms achieving k-clustering, (f,g)-alliance construction, and ranking. For every of these problems, we prove the correctness of our solutions. Moreover, we analyze their time and space complexity using formal proofs and simulations. Finally, for the (f,g)-alliance problem, we consider the notion of safe convergence in addition to self-stabilization. It enforces the system to first quickly satisfy a specification that guarantees a minimum of conditions, and then to converge to a more stringent specification., Cette thèse s'intéresse à la construction auto-stabilisante de structures couvrantes dans un système réparti. L'auto-stabilisation est un paradigme pour la tolérance aux fautes dans les algorithmes répartis. Plus précisément, elle garantit que le système retrouve un comportement correct en temps fini après avoir été perturbé par des fautes transitoires. Notre modèle de système réparti se base sur des mémoires localement partagées pour la communication, des identifiants uniques pour briser les symétries et un ordonnanceur inéquitable, c'est-à-dire le plus faible des ordonnanceurs. Dans la mesure du possible, nous nous imposons d'utiliser les plus faibles hypothèses, afin d'obtenir les constructions les plus générales de structures couvrantes réparties. Nous présentons quatre algorithmes auto-stabilisants originaux pour le k-partitionnement, la construction d'une (f,g)-alliance et l'indexation. Pour chacun de ces problèmes, nous prouvons la correction de nos solutions. De plus, nous analysons leur complexité en temps et en espace à l'aide de preuves formelles et de simulations. Enfin, pour le problème de (f,g)-alliance, nous prenons en compte la notion de convergence sûre qui vient s'ajouter à celle d'auto-stabilisation. Elle garantit d'abord que le comportement du système assure rapidement un minimum de conditions, puis qu'il continue de converger jusqu'à se conformer à une spécification plus exigeante.