Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory.
The subject of the thesis is to study a model that enhances the original model of population protocols by introducing a (weak) notion of speed of the agents. In this model problems like mutual exclusion, group mutual exclusion, phase clocks and unison will be studied.
Moreover automatic transformers that allow to develop from a synchronous model to an asynchronous one or from a model without failures to a model tolerating failures, will be studied.
Another goal is to extend the already known results to a model in which the communications of an agent are restricted to a proper subset of all agents. In such a model, a problem like routing becomes crucial.
Context
The population protocol model, defined in Angluin et al (PODC 04) has received a lot of attention during the recent year. It has been proven that this model is rather limited, since the only computable function are those expressed in the Pressburger arithmetics.
Thus different extensions of the model have been proposed, like the addition of a powerful non-mobile agent (Beauquier et al., DISC 07) or the notion of speed (Beauquier et al., PODC 09). A strong relation exists between this extended model and the Delay Tolerant Network model (DTN), that is a very hot topic in networking.
Very few problems have been studied in the extended model and doing that is precisely the goal of the thesis.
Objectives
- Design algorithmic solution in the framework of mobile agents with speed, to problems like: mutual exclusion, group mutual exclusion, phase clocks and unison, election.
- Design automatic transformers (compilers) allowing to develop from a synchronous model to an asynchronous one or from a model without failures to a model tolerating failures.
- Extend the already known results, holding in a model in which an agent can communicate with any other agent, to a model in which the communications of an agent are restricted to a proper subset of all agents. In such a model, study the routing problem.
Work program
First year: bibliography, understanding of the state of the art, first approaches.
Second year: designing algorithmic solutions and proving them.
Third year: transformers, design of general tools, writing of the thesis.
Extra information
Prerequisite
Some familiarity with distributed computing and distributed algorithms (reference books are those of Gerard Tel or Nancy Lynch on distributed algorithms).
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
This is a purely algorithmic subject, no programming, no development. You can check your adequation to the topic by consulting any proceedings of the ACM conference "Principles of Distributed Computing" (PODC) or the complete paper at http://tx.technion.ac.il/~bjanna/main_BBCK_speed_pp.pdf.
Utilisateur
Joffroy.Beauquier
Créé
Jeudi 11 février 2010 11:12:11 CET
dernière modif.
Mardi 30 avril 2013 13:25:29 CEST
Fichiers joints
filename
créé
hits
filesize
Aucun fichier joint à cette fiche
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit Assistante
Stéphanie Druetta Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr