An anonymous ring network is a ring where all processors (vertices) are indistinguishable except for their input value. Initially, to each vertex of the ring is associated a value from a totally ordered set; thus, forming a multiset.In this paper, we consider the problem of sorting such a distributed multiset and we investigate its relationship with the election problem. We focus on the computability and the complexity of these problems, as well as on their interrelationship, providing strong characterizations, showing lower bounds, and establishing efficient upper bounds.

An anonymous ring network is a ring where all processors (vertices) are totally indistinguishable except for their input value. Initially, to each vertex of the ring is associated a value from a totally ordered set; thus, forming a multiset. In this paper we consider the problem of sorting such a distributed multiset and we investigate its relationship with the election problem. We focus on the computability and the complexity of these problems, as well as on their interrelationship, providing strong characterizations, showing lower bounds, and establishing efficient upper bounds.

Sorting Multisets in Anonymous Rings

LUCCIO, Flaminia;
2000-01-01

Abstract

An anonymous ring network is a ring where all processors (vertices) are totally indistinguishable except for their input value. Initially, to each vertex of the ring is associated a value from a totally ordered set; thus, forming a multiset. In this paper we consider the problem of sorting such a distributed multiset and we investigate its relationship with the election problem. We focus on the computability and the complexity of these problems, as well as on their interrelationship, providing strong characterizations, showing lower bounds, and establishing efficient upper bounds.
2000
IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS)
File in questo prodotto:
File Dimensione Formato  
ipdps00.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Accesso chiuso-personale
Dimensione 762.74 kB
Formato Adobe PDF
762.74 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/32324
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact