Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Verifying a Structured Peer-to-Peer Overlay Network: The Static Case
verfasst von : Johannes Borgström, Uwe Nestmann, Luc Onana, Dilian Gurov
Erschienen in: Global Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Structured peer-to-peer overlay networks are a class of algorithms that provide e.cient message routing for distributed applications using a sparsely connected communication network. In this paper, we formally verify a typical application running on a .xed 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 speci.cation 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 speci.cation. 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.