Broadcasting on Anonymous Unoriented Tori

摘要

We consider broadcasting on asynchronous anonymous totally unoriented n × m torus, where N = n · m is the number of nodes. We present a broadcasting algorithm with message complexity 1.43N + O(n+m) and prove the lower bound in the form 1.14N -O(1). This is an improvement over the previous 2N + O(√N) upper bound and 1.04N -O(√N) lower bound achieved by Diks, Kranakis and Pelc [DKP96]. Unlike the algorithm from [DKP96], our algorithm works also on non-square tori, does not require the knowledge of sizes n and m and uses only messages of size O(1) bits. This is the first known broadcasting algorithm on unoriented tori that does not use all edges.