Efficient distributed selection with bounded messages

Author

Negro, Alberto ; Santoro, Nicola ; Urrutia, Jorge

Author_Institution

Dipartimento di Sci. dell´´Inf., Salerno Univ., Italy

Volume

8

Issue

4

fYear

1997

fDate

4/1/1997 12:00:00 AM

Firstpage

397

Lastpage

401

Abstract

We consider the problem of selecting the Kth smallest element of a set distributed among the sites of a communication network when the size of messages is bounded; that is, each message is a packet which contains at most c bits, where c⩾1 is a constant. A general selection algorithm using packets is presented and its packet complexity is analyzed. Its complexity is shown to be a significant improvement for a large range of packet sizes over the existing bounds. The proposed technique is then instanciated for specific classes of network topologies; the resulting bounds either match or improve the ones of existing solutions for a large range of values of the packet size. Furthermore, it is bit optimal in star networks

Keywords

communication complexity; distributed algorithms; multiprocessor interconnection networks; Kth smallest element; bounded messages; communication network; distributed selection; general selection algorithm; network topologies; packet complexity; star networks; Algorithm design and analysis; Communication networks; Complexity theory; Computer Society; Computer science; Delay effects; Distributed algorithms; Distributed computing; Network topology; Sorting;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.588617

Filename

588617