Distributed multiple selection algorithm for peer-to-peer systems

Document Type

Journal article

Source Publication

Journal of Systems and Software

Publication Date

12-1-2005

Volume

78

Issue

3

First Page

234

Last Page

248

Publisher

Elsevier Inc.

Keywords

Multiple selection algorithm, intranet, web technologies, complexity analysis, distributed selection, peer-to-peer systems

Abstract

This paper presents an efficient distributed multiple selection algorithm designed to select multiple keys simultaneously from different data sets which are distributed to many computers in a peer-to-peer system. The communication time is usually much longer than the computation time and is thus a major criterion for measuring the performance of a distributed algorithm. The objective of this algorithm is to reduce the number of communication messages. The algorithm makes use of statistical knowledge and results in a smaller communication overhead compared with existing algorithms. In this algorithm, each computer will select keys as pivots (candidates for the answers) according to statistical knowledge and transmit them to other computers in the system. Each computer will compare each pivot with key values in its local file and respond by transmitting ranks to the originating computer. The originating computer will calculate the global ranks and verify whether the pivots are the answers. Each computer will broadcast once sequentially in each round. This broadcasting process will be repeated until all answers are found. Complexity analyses are presented to provide theoretical upper bounds of this algorithm. The correctness of the theoretical predication is verified by experiments with 40 computers connected using Web technologies.

DOI

10.1016/j.jss.2004.08.033

Print ISSN

01641212

E-ISSN

18731228

Publisher Statement

Copyright © 2004 Elsevier Inc

Access to external full text or publisher's version may require subscription.

Full-text Version

Publisher’s Version

Language

English

Recommended Citation

Loo, W. A. (2005). Distributed multiple selection algorithm for peer-to-peer systems. The Journal of Systems and Software, 78(3), 234-248. doi: 10.1016/j.jss.2004.08.033

Share

COinS