Change search
ReferencesLink to record
Permanent link

Direct link
A statistical theory of Chord under churn
Swedish Institute of Computer Science.
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
2005 (English)In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 3640, 93-103 p.Article in journal (Refereed) Published
Abstract [en]

Most earlier studies of DHTs under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation- based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different 'types' and the implications this will have for the functioning of DHTs in general.

Place, publisher, year, edition, pages
2005. Vol. 3640, 93-103 p.
Keyword [en]
Computer science, Computer simulation, Performance, Statistical mechanics, Chord system, Investigation tools, Master-equation-based approach
National Category
Computer Engineering
URN: urn:nbn:se:kth:diva-25147DOI: 10.1007/11558989_9ISI: 000234463200008ScopusID: 2-s2.0-33646024301OAI: diva2:356110
QC 20101011. IngÄr i 4th International Workshop on Peer-to-Peer Systems, IPTPS 2005Available from: 2010-10-11 Created: 2010-10-11 Last updated: 2010-10-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Krishnamurthy, SupriyaEl-Ansary, SamehAurell, ErikHaridi, Seif
By organisation
PhysicsMicroelectronics and Information Technology, IMIT
In the same journal
Lecture Notes in Computer Science
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link