A gap theorem for the anonymous torus

We characterize the class of functions computable on an anonymous torus, where each processor does not know the dimension n of the torus but only an upper bound m of n. We show that any computable function can be computed exchanging O(n root m) messages. Surprisingly, we prove a ''gap'' theorem showing that all non-constant computable functions have message complexity Omega(n root m). From these results we obtain that to compute any non-constant computable function, the input collection algorithm is the optimal one. Analogous results are obtained for the case that the torus is non-square and for the anonymous ring.