Optimal Computation of Global Sensitive Functions in Fast Networks
Israel Cidon, Inder Gopal and Shay Kutten
Abstract:
The common practice in distributed algorithms research was to assume that the computation time is zero, and assign
a cost only to the communication. This was justified at the times that the communication was the bottleneck of a
network. However, lately there has been a dramatic increase in the capacity of communication links so that we can
no longer make this assumption.
In this paper we fred optimal algorithms for distributed computation of "global sensitive" functions in the case
that the computation time is some given P, and the communication time is some given C. (Roughly speaking, a
global sensitive function is one that depends on each of its inputs.)