Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Physics-inspired performance evaluation of DHTs
Distributed Systems Laboratory, SICS Swedish Institute of Computer Science.
KTH, School of Engineering Sciences (SCI), Physics.
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.ORCID iD: 0000-0002-6718-0144
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In the majority of structured peer-to-peer overlay networks a graph with a desirable topology is constructed. In most cases, the graph is maintained by a periodic activity performed by each node in the graph to preserve the desirable structure in face of the continuous change of the set of nodes. The interaction of the autonomous periodic activities of the nodes renders the performance analysis of such systems complex and simulation of scales of interest can be prohibitive. Physicists, however, are accustomed to dealing with scale by characterizing a system using intensive variables, i.e. variables that are size independent. The approach has proved its usefulness when applied to satisfiability theory. This work is the first attempt to apply it in the area of distributed systems. The contribution of this paper is two-fold. First, we describe a methodology to be used for analyzing the performance of large scale distributed systems. Second, we show how we applied the methodology to find two intensive variables that describe the characteristic behavior of the Chord overlay network, the variables are: 1) The density of nodes in the identifier space and 2) The ratio of the magnitude of perturbation of the network (joins/failures) to the magnitude of periodic stabilization of the network.

Keyword [en]
DHT performance, Structured Overlay networks, Data Collapse, Complex Systems
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:kth:diva-25101OAI: oai:DiVA.org:kth-25101DiVA: diva2:355799
Note
QC 20101008. Baserad på följande tre artiklar: Erik Aurell and Sameh El-Ansary A Physics-Style Approach to Scalability of Distributed Systems. LNCS Post-Proceedings of the Global Computing 2004Workshop (March 2004), Rovereto, Italy. Sameh El-Ansary, Erik Aurell, Per Brand and Seif Haridi, Experience with a physics-style approach for the study of self properties in structured overlay networks, In the International Workshop on Self-* Properties in Complex Information Systems, (May 2004), Bertinoro, Italy Sameh El-Ansary, Erik Aurell and Seif Haridi, A Physics inspired Performance Evaluation of a Structured Peer-to-Peer Overlay Networks, In the International Conference on Parallel and Distributed Computing and Networks (PDCN 2005), Innsbruck, Austria, February , 2005 Available from: 2010-10-08 Created: 2010-10-08 Last updated: 2010-10-08Bibliographically approved
In thesis
1. Designs and analyses in structured peer-to-peer systems
Open this publication in new window or tab >>Designs and analyses in structured peer-to-peer systems
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Peer-to-Peer (P2P) computing is a recent hot topic in the areas of networking and distributed systems. Work on P2P computing was triggered by a number of ad-hoc systems that made the concept popular. Later, academic research efforts started to investigate P2P computing issues based on scientific principles. Some of that research produced a number of structured P2P systems that were collectively referred to by the term ``Distributed Hash Tables'' (DHTs). However, the research occurred in a diversified way leading to the appearance of similar concepts yet lacking a common perspective and not heavily analyzed. In this thesis we present a number of papers representing our research results in the area of structured P2P systems grouped as two sets labeled respectively ``Designs'' and ``Analyses''.

The contribution of the first set of papers is as follows. First, we present the principle of distributed k-ary search (DKS) and argue that it serves as a framework for most of the recent P2P systems known as DHTs. That is, given the DKS framework, understanding existing DHT systems is done simply by seeing how they are instances of that framework. We argue that by perceiving systems as instances of the DKS framework, one can optimize some of them. We illustrate that by applying the framework to the Chord system, one of the most established DHT systems. Second, We show how the DKS framework helps in the design of P2P algorithms by two examples: (a) The DKS(n;k;f) system which is a system designed from the beginning on the principles of distributed k-ary search. (b) Two broadcast algorithms that take advantage of the distributed k-ary search tree.

The contribution of the second set of papers is as follows. We account for two approaches that we used to evaluate the performance of a particular class of DHTs, namely the one adopting periodic stabilization for topology maintenance. The first approach was of an intrinsic empirical nature. In that approach, we tried to perceive a DHT as a physical system and account for its properties in a size-independent manner. The second approach was of a more analytical nature. In this approach we applied the technique of Master equations, which is a widely used technique in the analysis of natural systems. The application of the technique lead to a highly accurate description of the behavior of structured overlays.

Additionally, the thesis contains a primer on structured P2P systems that tries to capture the main ideas that are prevailing in the field and enumerates a subset of the current hot and open research issues.

Place, publisher, year, edition, pages
Stockholm: KTH, 2005. 229 p.
Series
Trita-IMIT. LECS, ISSN 1651-4076 ; 05:02
Series
SICS Dissertation Series, ISSN 1101-1335 ; 38
Keyword
Datorsystem, Datorsystem
National Category
Computer Engineering
Identifiers
urn:nbn:se:kth:diva-264 (URN)
Public defence
2005-06-10, Sal D, KTH Forum, 10:00
Opponent
Supervisors
Note
QC 20101008Available from: 2005-06-07 Created: 2005-06-07 Last updated: 2010-10-11Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Haridi, Seif

Search in DiVA

By author/editor
El-Ansary, SamehAurell, ErikHaridi, Seif
By organisation
PhysicsMicroelectronics and Information Technology, IMIT
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 144 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf