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.