Chargement...
 

Parallelism-High Performance Computing-Grid

Domaine
Parallelism-High Performance Computing-Grid
Domain - extra
Distributed Computing
Année
2014
Starting
september 2014
État
Open
Sujet
Open Problems for Population Protocols
Thesis advisor
BEAUQUIER Joffroy
Co-advisors
BURMAN Janna
Laboratory
Collaborations
Abstract
Population Protocols are an elegant model for networks of tiny mobile agents. Since their introduction in 2004, a lot of papers have been published about Population Protocols. Numerous issues remain open and the subject of this thesis is to attack them. Among them, one can mention the equivalence between deterministic and non-deterministic population protocols, the issues related to the weakest oracles for solving leader election or consensus, the extension of the results obtained for complete communication graphs to arbitrary graphs for the extension with cover times.
Context
Population Protocols have been introduced in 2004 by Angluin and al. The first studies concern principally their computing power and a nice characterization has been obtained. The team at LRI works on this topic since about five years, in the perspective to design solutions to basic distributed system tasks (leader election, mutual exclusion, consensus, synchronizers, ...), in the extension of Population Protocols by cover times.
Objectives
Solve some open problems and answer some conjectures about Population Protocols.
Work program
The first year will focus onto the equivalence between deterministic and non-deterministic Population Protocols, the second year on oracles (and weakest oracles) for solving some system tasks and the third year on the extension of previous results about Population Protocols with cover time to arbitrary communication graphs.
Extra information
Prerequisite
The module "Tolerance aux défaillances dans les systèmes répartis" of the M2R NSI at Paris-Sud university or any equivalent module.

For an idea about the type of the proposed research, see :
http://tx.technion.ac.il/~bjanna/main_BBCK_speed_pp.pdf.
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
Utilisateur
Joffroy.Beauquier
Créé
Mardi 30 avril 2013 09:50:07 CEST
dernière modif.
Mardi 11 mars 2014 18:58:48 CET

Fichiers joints

 filenamecrééhitsfilesize 
Aucun fichier joint à cette fiche


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