A semi-structured overlay network for large-scale peer-to-peer systems

Kousaku Kimura, Satoshi Amamiya, Tsunenori Mine, Makoto Amamiya

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Peer-to-peer (P2P) communication and computing frameworks are important for constructing robust large-scale distributed systems. Overlay network systems use distributed hash-table (DHT) to provide scalable and efficient node search capabilities. However, the DHT-based method has a problem for the maintenance cost of dynamically changing large-scale-network, in which nodes are frequently joining and leaving. This paper proposes a novel technique of P2P communication path management. The proposed technique devises a robust semi-structured overlay network called Ordered Tree with Tuft (OTT for short). OTT provides not only efficient node searching, but also low-cost self-maintenance capabilities for the dynamically changing network. In this method, joining and leaving of a node are managed in O(1) with high probability. Furthermore, the proposed OTT-based technique can find and construct a path shorter than that on the normal ordered tree, by setting up bypass links between remote nodes on OTT.

Original languageEnglish
Title of host publicationAgents and Peer-to-Peer Computing - 8th International Workshop, AP2PC 2009, Revised Selected Papers
Number of pages12
Publication statusPublished - 2012
Event8th International Workshop on Agents and Peer-to-Peer Computing, AP2PC 2009 - Budapest, Hungary
Duration: May 11 2009May 11 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6573 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Workshop on Agents and Peer-to-Peer Computing, AP2PC 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A semi-structured overlay network for large-scale peer-to-peer systems'. Together they form a unique fingerprint.

Cite this