Distributed multiple selection algorithm for peer-to-peer systems

Wai Sing, Alfred LOO

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

5 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)234-248
Number of pages15
JournalJournal of Systems and Software
Volume78
Issue number3
DOIs
Publication statusPublished - 1 Dec 2005

Fingerprint

Communication
Broadcasting
Parallel algorithms
Computer systems
Experiments

Keywords

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

Cite this

LOO, Wai Sing, Alfred. / Distributed multiple selection algorithm for peer-to-peer systems. In: Journal of Systems and Software. 2005 ; Vol. 78, No. 3. pp. 234-248.
@article{0a4c3191c8434af6a9db50922c549eba,
title = "Distributed multiple selection algorithm for 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.",
keywords = "Multiple selection algorithm, complexity analysis, distributed selection, intranet, peer-to-peer systems, web technologies",
author = "LOO, {Wai Sing, Alfred}",
year = "2005",
month = "12",
day = "1",
doi = "10.1016/j.jss.2004.08.033",
language = "English",
volume = "78",
pages = "234--248",
journal = "Journal of Systems and Software",
issn = "0164-1212",
publisher = "Elsevier Inc.",
number = "3",

}

Distributed multiple selection algorithm for peer-to-peer systems. / LOO, Wai Sing, Alfred.

In: Journal of Systems and Software, Vol. 78, No. 3, 01.12.2005, p. 234-248.

Research output: Journal PublicationsJournal Article (refereed)Researchpeer-review

TY - JOUR

T1 - Distributed multiple selection algorithm for peer-to-peer systems

AU - LOO, Wai Sing, Alfred

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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.

AB - 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.

KW - Multiple selection algorithm

KW - complexity analysis

KW - distributed selection

KW - intranet

KW - peer-to-peer systems

KW - web technologies

UR - http://commons.ln.edu.hk/sw_master/168

U2 - 10.1016/j.jss.2004.08.033

DO - 10.1016/j.jss.2004.08.033

M3 - Journal Article (refereed)

VL - 78

SP - 234

EP - 248

JO - Journal of Systems and Software

JF - Journal of Systems and Software

SN - 0164-1212

IS - 3

ER -