In an anonymous ring of n processors, all processors are totally indistinguishable except for their input values. These values are not necessarily distinct, i.e., they form a multiset, and this makes many problems particularly difficult. We consider the problem of distributively sorting such a multiset on the ring, and we give a complete characterization of the relationship with the problems of leader election for vertices and edges. For Boolean input values and prime n, we also establish a lower bound, and a reasonably close upper bound on the message complexity valid for sorting and leader election.

Anonymous ring, Distributed computing, Leader election, Multisets, Sorting
Journal of Parallel and Distributed Computing
School of Computer Science

Flocchini, P. (Paola), Kranakis, E, Krizanc, D. (Danny), Luccio, F.L. (Flaminia L.), & Santoro, N. (2004). Sorting and election in anonymous asynchronous rings. Journal of Parallel and Distributed Computing, 64(2), 254–265. doi:10.1016/j.jpdc.2003.11.007