Cette th`ese se concentre sur des bases th´eoriques utiles pour l'analyse d'algorithmes et de protocoles<br />pour des syst`emes r´epartis modernes. Deux caract´eristiques importantes des mod`eles pour<br />ces syst`emes sont les probabilit´es et la mobilit´e typ´ee : des probabilit´es peuvent ˆetre utilis´ees pour<br />quantifier des comportements incertains ou impr´evisibles, et des types peuvent ˆetre utilis´es pour<br />garantir des comportements sˆurs dans des syst`emes mobiles. Dans cette th`ese nous d´eveloppons<br />des techniques alg´ebriques et des techniques bas´ees sur les types pour l'´etude comportementale des<br />processus probabilistes et mobiles.<br /><br />Dans la premi`ere partie de la th`ese nous ´etudions la th´eorie alg´ebrique d'un calcul de processus<br />qui combine les comportements non-d´eterministe et probabiliste dans le mod`ele des automates probabilistes<br />propos´es par Segala et Lynch. Nous consid´erons diverses ´equivalences comportementales<br />fortes et faibles, et nous fournissons des axiomatisations compl`etes pour des processus `a ´etats finis,<br />limit´ees `a la r´ecursion gard´ee dans le cas des ´equivalences faibles.<br /><br />Dans la deuxi`eme partie de la th`ese nous ´etudions la th´eorie alg´ebrique du -calcul en pr´esence<br />des types de capacit´es, qui sont tr`es utiles dans les calculs de processus mobiles. Les types de<br />capacit´es distinguent la capacit´e de lire sur un canal, la capacit´e d'´ecrire sur un canal, et la capacit´e<br />de lire et d'´ecrire `a la fois. Ils introduisent ´egalement une relation de sous-typage naturelle et<br />puissante. Nous consid´erons deux variantes de la bisimilarit´e typ´ee, dans leurs versions retard´ees<br />et anticip´ees. Pour les deux variantes, nous donnons des axiomatisations compl`etes pour les termes<br />ferm´es. Pour une des deux variantes, nous fournissons une axiomatisation compl`ete pour tous les<br />termes finis.<br /><br />Dans la derni`ere partie de la th`ese nous d´eveloppons des techniques bas´ees sur les types pour<br />v´erifier la propri´et´e de terminaison de certains processus mobiles. Nous fournissons quatre syst`emes<br />de types pour garantir cette propri´et´e. Les syst`emes de types sont obtenus par des am´eliorations<br />successives des types du -calcul simplement typ´e. Les preuves de terminaison utilisent des techniques<br />employ´ees dans les syst`emes de r´e´ecriture. Ces syst`emes de types peuvent ˆetre utilis´es pour<br />raisonner sur le comportement de terminaison de quelques exemples non triviaux : les codages des<br />fonctions r´ecursives primitives, le protocole pour coder le choix s´epar´e en terme de composition<br />parall`ele, une table de symboles implement´ee comme une chaˆıne dynamique de cellules.<br /><br />Ces r´esultats ´etablissent des bases pour une future ´etude de mod`eles plus avanc´es qui peuvent<br />combiner des probabilit´es avec des types. Ils soulignent ´egalement la robustesse des techniques<br />alg´ebriques et de celles bas´ees sur les types pour le raisonnement comportemental.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00155225 |
| Date | 22 July 2005 |
| Creators | Deng, Yuxin |
| Publisher | École Nationale Supérieure des Mines de Paris |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.01 seconds