On Message Complexity of Extrema Propagation Techniques

摘要

In this paper we discuss the message complexity of some variants of the Extrema Propagation techniques in wireless networks. We show that the average message complexity, counted as the number of messages sent by each given node, is O(log n), where n denotes the size of the network. We indicate the connection between our problem and the well known and deeply studied problem of the number of records in a random permutation. We generalize this problem onto an arbitrary simple and locally finite graphs, prove some basic theorems and find message complexity for some classical graphs such us lines, circles, grids and trees.