Gap theorems for distributed computing
Shlomo Moran, Manfred K. Warmuth · 1986
Consider a ring of n anonymous processors, i.e. the processors have no id's.Each processor receives an input string and the ring is to compute a function of the circular input configuration in the asynchronous bidirectional model of computation.The complexity of an algorithm is the number of bits or the number of messages sent in the worst case.The complexity of a function is the lowest complexity of any algorithm that computes that function.If the function value is constant for all input configurations, the processors do not need to send any messages (complexity zero).On the other hand, we prove that any non-constant function has bit complexity f~(n logn ) for anonymous rings.There are non-constant functions that reach the upper end of the gap, i.e. we exhibit a non-constant function of bit complexity O (nlogn).The same gap for the bit complexity of non-constant functions remains even if the processors have distinct id's, provided that the id's are taken from a large enough domain.For the case of using the number of messages sent rather than the number of bits as the complexity measure, we present a nonconstant function that can be computed with O (n log* n ) messages on an anonymous ring.