kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
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: Electronic Notes in Theoretical Computer Science, E-ISSN 1571-0661, Vol. 181, no 1, p. 35-47Article 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, p. 35-47
Keywords [en]
Peer-to-peer systems, verification, process algebra.
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-50774DOI: 10.1016/j.entcs.2007.01.052ISI: 000214244400004Scopus ID: 2-s2.0-34250218171OAI: oai:DiVA.org:kth-50774DiVA, id: diva2:462652
Note
QC 20111209Available from: 2011-12-07 Created: 2011-12-07 Last updated: 2024-07-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gurov, Dilian

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
Electronic Notes in Theoretical Computer Science
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 116 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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