Trade-off Between Computational Power and Common Knowledge in Anonymous Rings*
Palo Ferragina, Angelo Monti, Alessandro Roncato · McGill-Queen's University Press eBooks · 1995
We give an exact characterization of the My of functions that can be computed distributively in an anonymous ring, diversifying the type of knowledge of the processors about the inpat configuration I , where I is the sequence of processor labels, | I | = n . We consider two kinds of knowledge, namely an upper-bound M on n model R M ), and the exact number V of distinct labels in I (model R V ). Moreover we prove that such fo11ctios can be computed on the asynchronous R M ( R V ) exchanging O ( nM ) ( O ( n min {log n , V })) messages. We show that the general protocol used to attain the above results cannot be improved with respect to the message complexity, since there are functions requiring Ω ( nM ) ( Ω ( n min (log n , V })) messages, respectively. Furthermore, we investigate the problem of electing a leader in R M and R V using randomization.