.png){kind=icon}
.png){kind=icon}
Return
Sorting and election in anonymous asynchronous rings
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2003.11.007.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2003 Elsevier Inc. All rights reserved.
Keywords:
distributed computing
sorting
leader election
multisets
anonymous ring
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available