2004-02-01
Sorting and election in anonymous asynchronous rings
Publication
Publication
Journal of Parallel and Distributed Computing , Volume 64 - Issue 2 p. 254- 265
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.
Additional Metadata | |
---|---|
Anonymous ring, Distributed computing, Leader election, Multisets, Sorting | |
dx.doi.org/10.1016/j.jpdc.2003.11.007 | |
Journal of Parallel and Distributed Computing | |
Organisation | 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
|