On the complexity of global computation in the presence of link failures: the general case

The paper presents Ω(m log n) and Ω( mn) message lower bounds on the problem of computing a global sensitive function in bidirectional networks with link failures (i.e., dynamically changing topology), where n and m are the total number of nodes and links in the network. Then Ω(m log n) lower bound is under the assumption that n is a-priori known to the nodes, while the second bound is for the case in which such knowledge is not available . A global sensitive function of n variables is a function that may not be computed without the knowledge of the values of all the n variables (e.g. maximum, sum, etc.). Thus, computing such a function at one node of a distributed network requires this node to communicate with every other node in the network. Though lower bounds higher than Ω(m) messages are known for this problem in the context of link failures, none holds for dense bidirectional networks. Moreover, the authors are not aware of any other non-trivial lower bound higher than Ω(m) for dense bidirectional networks