Broadcasting in Unlabeled Tori
Krzysztof Diks, Evangelos Kranakis, Andrzej Pelc · Parallel Processing Letters · 1998
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled torus: neither nodes nor links have a priori assigned labels but they know the topology and the size of the torus. Nodes can send messages of arbitrary size and we are interested in minimizing the total number of messages. A naive broadcasting algorithm in a n × n totally unlabeled torus uses 3n 2 + 1 messages, while the obvious lower bound is n 2 - 1. The main result of this paper is a broadcasting algorithm using 2n 2 + O(n) messages. We also give a lower bound of 1.04n 2 - O(n) messages. This is the first result on message complexity of broadcasting in totally unlabeled networks.