Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Finding the extrema of a distributed multiset
| |
|
Finding the extrema of a distributed multiset P. Alimonti1, P. Flocchini2 and N. Santoro3
| (1) |
Dip. Informatica Sistemistica, Università di Roma  la Sapienza , Italy |
| (2) |
Dip. di Scienze dell'informazione, Università di Milano, Italy |
| (3) |
School of Computer Science, Carleton University, Canada |
Abstract
We consider the problem of finding the extrema of a distributed multiset in a ring; that is, of determining the minimum and the maximum values, x
min and x
max, of a multiset X={x
0, x 2, ..., x
n}-1}, whose elements are drawn from a totally ordered universe U and stored at the n entities of a ring network.
This problem is unsolvable if the ring size is not known to the entities, and has complexity  (n
2) in the case of asynchronous rings of known size.
We show that, in synchronous rings of known size, this problem can always be solved in O((c+ log n) · n) bits and O(n · c · x
1/c) time for any integer c> 0, where x=Max{¦xmin¦, ¦xmax¦}. The previous solutions required O(n
2) bits and the same amount of time.
Based on these results, we also present a bit optimal solution to the problem of finding the multiplicity of the extrema.
Work partially supported by: ESPRIT III, Basic Research Action Program ALCOM 2; Ministero dell'Università e della Ricerca Scientifica e Tecnologica (Italy), Project  Algoritmi, Modelli di Calcolo e Strutture Informative ; Consiglio Nazionale delle Ricerche (Italy); and Natural Sciences and Engineering Research Council (Canada), under grant A241 5.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|