Energy Efficient Naming in Beeping Networks

摘要

A single-hop beeping network is a distributed communication model in which each station can communicate with all other but only by 1 — bit messages called beeps. In this paper, we: focus on resolving two fundamental distributed computing issues: the naming and the counting on this model. Especially, we are interested in optimizing energy complexity and running time for those issues. Our contribution is to have design randomized algorithms with an optimal running time of 0(n log n) and optimal O(log n) energy complexity whether for the naming or the counting for a single-hop beeping network of n stations.