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
Verifying a Structured Peer-to-Peer Overlay Network: The Static Case
EPFL.
EPFL.
SICS.
SICS.
2005 (English)In: Global Computing: IST/FET International Workshop, GC 2004 Rovereto, Italy, March 9-12, 2004: Revised Selected Papers / [ed] C. Priami and P. Quaglia, Berlin Heidelberg: Springer Berlin/Heidelberg, 2005, 250-265 p.Conference paper, Published paper (Refereed)
Abstract [en]

Structured peer-to-peer overlay networks are a class of algorithms that provide efficient message routing for distributed applications using a sparsely connected communication network. In this paper, we formally verify a typical application running on a fixed set of nodes. This work is the foundation for studies of a more dynamic system.

We identify a value and expression language for a value-passing CCS that allows us to formally model a distributed hash table implemented over a static DKS overlay network. We then provide a specification of the lookup operation in the same language, allowing us to formally verify the correctness of the system in terms of observational equivalence between implementation and specification. For the proof, we employ an abstract notation for reachable states that allows us to work conveniently up to structural congruence, thus drastically reducing the number and shape of states to consider. The structure and techniques of the correctness proof are reusable for other overlay networks. 

Place, publisher, year, edition, pages
Berlin Heidelberg: Springer Berlin/Heidelberg, 2005. 250-265 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 3267
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-161486DOI: 10.1007/978-3-540-31794-4_13ISBN: 3-540-24101-9 (print)OAI: oai:DiVA.org:uu-161486DiVA: diva2:456283
Conference
Global Computing, IST/FET International Workshop, March 9-12, 2004, Rovereto, Italy
Available from: 2011-12-06 Created: 2011-11-14 Last updated: 2011-12-06Bibliographically approved

Open Access in DiVA

fulltext(497 kB)79 downloads
File information
File name FULLTEXT02.pdfFile size 497 kBChecksum SHA-512
6a71901cd9a44317d5257d842737586a4efb3d11c184a88e62e644509544e1f8394eb2abae9a6fc04c1523c7064d3b649ecfb0f0871e1d10f856fb8031cd5a31
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Borgström, Johannes
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 79 downloads
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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 416 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