Time-optimal information exchange on multiple channels

Abstract

This paper presents an efficient algorithm for detecting and disseminating information in a single-hop multi-channel network: k arbitrary nodes have information they want to share with the entire network. Neither the nodes that have information nor the number k of these nodes are known initially. This communication primitive lies between the two other fundamental primitives regarding information dissemination, broadcasting (one-to-all communication) and gossiping (total information exchange). The time complexity of the information exchange algorithm we present in this paper is linear in the number of information items and thus asymptotically optimal with respect to time. The algorithm does not require collision detection and thanks to using several channels the lower bound of Ω(k+log n) established for single-channel communication can be broken.