Decentralized communication and beep model

Overview & Synopsis

This thesis gathers several works on distributed communication problems. In particular, we focus on designing randomized distributed algorithms addressing the naming, the counting, the broadcasting and the leader election problems. The algorithms presented in this thesis are designed to resolve these problems on single-hop and multi-hop radio and beeping networks. We focus on optimizing the time complexity and the energy complexity of these algorithms. A commonly known principle for designing distributed random- ized algorithms makes each device of the network decide which computation to perform in a randomized manner at each time slot of the execution of the algorithm. Hence, we propose a new paradigm, which makes each node generate some random variables distributed following a specific distribution before communicating on the network in a distributed deterministic man- ner. Throughout this thesis, we use several random variable distributions to resolve each problem after the other. We also propose a new witnessing paradigm to help us optimize the energy complexity of the algorithms. The first part of the thesis (the first three chapters) provides the description of the models, problems, existing algorithms and complexity measures con- sidered in the thesis. The second part presents the new algorithms designed to resolve the considered problems.