Loading...
 
[Show/Hide Left Column]

Sujets Help

Print History View Items
No Tabs
ViewCommentsAttachments (0)

View Item

Domain Parallelism-High Performance Computing-Grid
Domain - extra Distributed Computing
Year 2014
Starting september 2014
Status Open
Subject Open Problems for Population Protocols
Thesis advisor BEAUQUIER Joffroy
Co-advisors BURMAN Janna
Laboratory LRI ParSys
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.
Details
Expected funding Institutional funding
Status of funding Expected
Candidates
user Joffroy.Beauquier
Created Tuesday 30 of April, 2013 09:50:07 CEST
LastModif Tuesday 11 of March, 2014 18:58:48 CET


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 at lri.fr