Ranking a set of numbers plays a key role in many application areas such as signal processing, statistics, computer science and so on. Distributed algorithms for ranking have been proposed in the computer science literature first for tree networks. Extension to general networks has been performed by constructing a spanning tree, which can be done in a distributed manner. In this paper we propose and analyze a gossip algorithm for distributed ranking. The advantage of the proposed algorithm is, on the one hand, its inherent robustness to changes and/or failures in the network and, on the other, its implementation simplicity. The algorithm is proved to converge, in the sense of giving the correct ranking, in finite time with probability one.

Gossip algorithms for distributed ranking

CHIUSO, ALESSANDRO;SCHENATO, LUCA;ZAMPIERI, SANDRO
2011

Abstract

Ranking a set of numbers plays a key role in many application areas such as signal processing, statistics, computer science and so on. Distributed algorithms for ranking have been proposed in the computer science literature first for tree networks. Extension to general networks has been performed by constructing a spanning tree, which can be done in a distributed manner. In this paper we propose and analyze a gossip algorithm for distributed ranking. The advantage of the proposed algorithm is, on the one hand, its inherent robustness to changes and/or failures in the network and, on the other, its implementation simplicity. The algorithm is proved to converge, in the sense of giving the correct ranking, in finite time with probability one.
Proc. of the American Control Conference
9781457700804
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS 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/11577/2440723
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 5
social impact