THÈSE D'UNIVERSITÉ :L'analyse d'exécutions réparties en utilisant la théorie de l'ordre
THÈSE D'UNIVERSITÉ :Guy-Vincent Jourdan
Octobre 1995
Résumé
L'informatique d'aujourd'hui est souvent une informatique
répartie. Pourtant, la conception, la mise au point et le test
d'applications distribuées restent problématiques. Dans cette
thèse, nous étudions la modélisation de telles
applications par la théorie de l'ordre. Ce modèle est
utilisé pour analyser une exécution distribuée.
Une exécution distribuée peut être vue comme un ensemble
partiellement ordonné d'événements observables. Nous
commençons notre étude par une évaluation des codages
existant, et fournissons une méthode originale : le codage
incrémental des dépendances transitives. Nous nous
intéressons ensuite à la manipulation dynamique de structures
ordonnées. Nous proposons deux algorithmes, un algorithme de
construction à la volée du treillis des idéaux d'un ordre
(ou treillis des états d'une exécution) et un algorithme de
construction à la volée du treillis des antichaînes
maximales d'un ordre. Nous poursuivons ce document avec une étude sur
l'insertion de procédures de vérification au c{oe}ur des
manipulations de structures. Deux approches sont considérées :
une vérification centralisée et une vérification
superposée à l'exécution. Nous concluons ce document par
un chapitre dédié au problème du dessin d'ensembles
ordonnés.
PhD THESIS:Guy-Vincent Jourdan
October 1995
Abstract
Computations are often distributed. Yet, designing, debugging and
testingdistributed systems is difficult. In this thesis, we study such systems
using the order theory. This model is used to analyze distributed computations.
A distributed computation can be seen as a partially ordered set of
observableevents. We first evaluate existing codings, and provide a new one:
theincremental coding of transitive dependencies. We then study
dynamicmanipulations of orders. We provides two on-line algorithms, an
algorithm tobuild on-line the lattice of ideals of an order (or states lattice
of anexecution) and an algorithm to build on-line the lattice of maximal
antichains of an order. Then, we study on-line checking algorithms on orders.
We give acentralized algorithm as well as a superimposed one. We conclude this
thesiswith a chapter on order drawing.