文章基本信息

标题：Communicating with Beeps
本地全文：下载
作者：Artur Czumaj ; Peter Davies
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：46
页码：1-16
DOI：10.4230/LIPIcs.OPODIS.2015.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The beep model is a very weak communications model in which devices in a network can communicate only via beeps and silence. As a result of its weak assumptions, it has broad applicability to many different implementations of communications networks. This comes at the cost of a restrictive environment for algorithm design. Despite being only recently introduced, the beep model has received considerable attention, in part due to its relationship with other communication models such as that of ad-hoc radio networks. However, there has been no definitive published result for several fundamental tasks in the model. We aim to rectify this with our paper. We present algorithms for the tasks of broadcast, gossiping, and multi-broadcast, and also, as intermediary results, means of depth-first search and diameter estimation. Our O(D+log(M)-time algorithm for broadcasting is a simple formalization of a concept known as beep waves, and is asymptotically optimal. We give an O(n*log(L))-time depth-first search procedure, and show how this can be used as the basis for an O(n*log(L*M))-time gossiping algorithm. Finally, we approach the more general problem of multi-broadcast. We differentiate between two variants of this problem: one where nodes must know the origin of all source messages, and another where this information is not required. In the first instance we achieve an algorithm running in time O(k*log((L*M)/k)+D*log(L)), and in the second an O(k*log(M/k)+D*log(L))-time algorithm (or O(M+D*log(L)) when M k and M <= k respectively. These lower bounds demonstrate that our algorithms are optimal except for the D*log(L) additive term. In these running-time expressions, n represents network size, D network diameter, L range of node labels, M range of source messages, and k number of sources. Our algorithms are all explicit, deterministic, and practical, and give efficient means of communication while making arguably the minimum possible assumptions about the network.
关键词：Beep model; Communication networks; Broadcasting; Gossiping; Leader election