Delay-bounded range queries in DHT-based peer-to-peer systems

Dongsheng Li; Jiannong Cao; Xicheng Lu; Chun Chung Chan; Baosheng Wang; Jinshu Su; Hong Va Leong; Alvin T.S. Chan

doi:10.1109/ICDCS.2006.26

Delay-bounded range queries in DHT-based peer-to-peer systems

Dongsheng Li, Jiannong Cao, Xicheng Lu, Chun Chung Chan, Baosheng Wang, Jinshu Su, Hong Va Leong, Alvin T.S. Chan

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

25 Citations (Scopus)

Abstract

Many general range query schemes for DHT-based peer-to-peer (P2P) systems have been proposed, which do not need to modify the underlying DHTs, However, most existing works have the query delay depending on both the scale of the system and the size of the query space or the specific query, and thus cannot guarantee to return the query results in a bounded delay. In this paper, we propose Armada, an efficient general range query scheme to support single-attribute and multiple-attribute range queries. Armada is the first delay-bounded range query scheme over constant-degree DHTs, and can return the results for any range query within 2logN hops in a P2P system with N peers. Results of analysis and simulations show that the average delay of Armada is less than logN, and the average message cost of single-attribute range queries is about logN+2n-2 (n is the number of peers that intersect with the query). These results are very close to the lower bounds on delay and message cost of range queries over constant-degree DHTs.

Original language	English
Title of host publication	26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006
Volume	2006
DOIs	https://doi.org/10.1109/ICDCS.2006.26
Publication status	Published - 1 Dec 2006
Event	26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006 - Lisboa, Portugal Duration: 4 Jul 2006 → 7 Jul 2006

Conference

Conference	26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006
Country/Territory	Portugal
City	Lisboa
Period	4/07/06 → 7/07/06

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

More information

10.1109/ICDCS.2006.26

http://hdl.handle.net/10397/857

Cite this

@inproceedings{90ec0aa6098f493a8de90c14b72b861d,

title = "Delay-bounded range queries in DHT-based peer-to-peer systems",

abstract = "Many general range query schemes for DHT-based peer-to-peer (P2P) systems have been proposed, which do not need to modify the underlying DHTs, However, most existing works have the query delay depending on both the scale of the system and the size of the query space or the specific query, and thus cannot guarantee to return the query results in a bounded delay. In this paper, we propose Armada, an efficient general range query scheme to support single-attribute and multiple-attribute range queries. Armada is the first delay-bounded range query scheme over constant-degree DHTs, and can return the results for any range query within 2logN hops in a P2P system with N peers. Results of analysis and simulations show that the average delay of Armada is less than logN, and the average message cost of single-attribute range queries is about logN+2n-2 (n is the number of peers that intersect with the query). These results are very close to the lower bounds on delay and message cost of range queries over constant-degree DHTs.",

author = "Dongsheng Li and Jiannong Cao and Xicheng Lu and Chan, {Chun Chung} and Baosheng Wang and Jinshu Su and Leong, {Hong Va} and Chan, {Alvin T.S.}",

year = "2006",

month = dec,

day = "1",

doi = "10.1109/ICDCS.2006.26",

language = "English",

isbn = "0769525407",

volume = "2006",

booktitle = "26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006",

note = "26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006 ; Conference date: 04-07-2006 Through 07-07-2006",

}

Li, D, Cao, J, Lu, X, Chan, CC, Wang, B, Su, J, Leong, HV & Chan, ATS 2006, Delay-bounded range queries in DHT-based peer-to-peer systems. in 26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006. vol. 2006, 1648851, 26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006, Lisboa, Portugal, 4/07/06. https://doi.org/10.1109/ICDCS.2006.26

Delay-bounded range queries in DHT-based peer-to-peer systems. / Li, Dongsheng; Cao, Jiannong; Lu, Xicheng et al.
26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006. Vol. 2006 2006. 1648851.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Delay-bounded range queries in DHT-based peer-to-peer systems

AU - Li, Dongsheng

AU - Cao, Jiannong

AU - Lu, Xicheng

AU - Chan, Chun Chung

AU - Wang, Baosheng

AU - Su, Jinshu

AU - Leong, Hong Va

AU - Chan, Alvin T.S.

PY - 2006/12/1

Y1 - 2006/12/1

N2 - Many general range query schemes for DHT-based peer-to-peer (P2P) systems have been proposed, which do not need to modify the underlying DHTs, However, most existing works have the query delay depending on both the scale of the system and the size of the query space or the specific query, and thus cannot guarantee to return the query results in a bounded delay. In this paper, we propose Armada, an efficient general range query scheme to support single-attribute and multiple-attribute range queries. Armada is the first delay-bounded range query scheme over constant-degree DHTs, and can return the results for any range query within 2logN hops in a P2P system with N peers. Results of analysis and simulations show that the average delay of Armada is less than logN, and the average message cost of single-attribute range queries is about logN+2n-2 (n is the number of peers that intersect with the query). These results are very close to the lower bounds on delay and message cost of range queries over constant-degree DHTs.

AB - Many general range query schemes for DHT-based peer-to-peer (P2P) systems have been proposed, which do not need to modify the underlying DHTs, However, most existing works have the query delay depending on both the scale of the system and the size of the query space or the specific query, and thus cannot guarantee to return the query results in a bounded delay. In this paper, we propose Armada, an efficient general range query scheme to support single-attribute and multiple-attribute range queries. Armada is the first delay-bounded range query scheme over constant-degree DHTs, and can return the results for any range query within 2logN hops in a P2P system with N peers. Results of analysis and simulations show that the average delay of Armada is less than logN, and the average message cost of single-attribute range queries is about logN+2n-2 (n is the number of peers that intersect with the query). These results are very close to the lower bounds on delay and message cost of range queries over constant-degree DHTs.

UR - http://www.scopus.com/inward/record.url?scp=33947628178&partnerID=8YFLogxK

U2 - 10.1109/ICDCS.2006.26

DO - 10.1109/ICDCS.2006.26

M3 - Conference article published in proceeding or book

SN - 0769525407

SN - 9780769525402

VL - 2006

BT - 26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006

T2 - 26th IEEE Internationa26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006

Y2 - 4 July 2006 through 7 July 2006

ER -

Delay-bounded range queries in DHT-based peer-to-peer systems

Abstract

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this