A Random-Walk Model for Distributed Computation in Energy-Limited Networks
Murat Alanyali, Venkatesh Saligrama, Onur Savas · 2006
We consider two distributed algorithms to compute functions that admit flexible decomposition in terms of pairwise computations. Under these algorithms a transmitting node becomes inactive and does not transmit further messages until it is reactivated by a message reception from another node. The algorithms thereby have sequential nature and bear a close relationship to random walks. We quantify their time and message complexities on the d-dimensional torus and establish substantial gains in message complexity with respect to gossip algorithms. The algorithms exhibit a favorable tradeoff between the two complexities in lower dimensions. In particular on the 2-dimensional torus with n nodes, time and per-node message complexities scale as Θ(n log n) and O((log n)) respectively, whereas both complexities scale as Ω(n) for gossip algorithms.