Change search
ReferencesLink to record
Permanent link

Direct link
Verification of Peer-to-peer Algorithms: A Case Study
KTH, School of Information and Communication Technology (ICT).
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-0074-8786
2007 (English)In: Electronical Notes in Theoretical Computer Science, ISSN 1571-0661, Vol. 181, no 1, 35-47 p.Article in journal (Refereed) Published
Abstract [en]

The problem of maintaining structured peer-to-peer (P2P) overlay networks in the presence of concurrent joins and failures of nodes is the subject of intensive research. The various algorithms underlying P2P systems are notoriously difficult to design and analyse. Thus, when verifying P2P algorithms, a real challenge is to find an adequate level of abstraction at which to model the algorithms and perform the verifications. In this paper, we propose an abstract model for structured P2P networks with ring topology. Our model is based on process algebra, which, with its well-developed theory, provides the right level of abstraction for the verification of many basic P2P algorithms. As a case study, we verify the correctness of the stabilization algorithm of Chord, one of the best-known P2P overlay networks. To show the correctness of the algorithm, we provide a specification and an implementation of the Chord system in process algebra and establish bisimulation equivalence between the two.

Place, publisher, year, edition, pages
2007. Vol. 181, no 1, 35-47 p.
Keyword [en]
Peer-to-peer systems, verification, process algebra.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-50774DOI: 10.1016/j.entcs.2007.01.052ScopusID: 2-s2.0-34250218171OAI: diva2:462652
QC 20111209Available from: 2011-12-07 Created: 2011-12-07 Last updated: 2011-12-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Bakhshi, RanaGurov, Dilian
By organisation
School of Information and Communication Technology (ICT)Theoretical Computer Science, TCS
In the same journal
Electronical Notes in Theoretical Computer Science
Computer and Information Science

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: 27 hits
ReferencesLink to record
Permanent link

Direct link