Specification Faithfulness in Networks with Rational Nodes

DSpace/Manakin Repository

Specification Faithfulness in Networks with Rational Nodes

Citable link to this page


Title: Specification Faithfulness in Networks with Rational Nodes
Author: Shneidman, Jeffrey; Parkes, David C.

Note: Order does not necessarily reflect citation order of authors.

Citation: Shneidman, Jeffrey and David C. Parkes. 2004. Specification faithfulness in networks with rational nodes. In Proceedings of the twenty-third annual ACM symposium on principles of distributed computing: PODC 2004: July 25-28, 2004, St. John's, Newfoundland, Canada, ed. ACM Special Interest Group for Algorithms and Computation Theory, and ACM Special Interest Group in Operating Systems, 88-97. New York, N.Y.: Association for Computing Machinery.
Full Text & Related Files:
Abstract: It is useful to prove that an implementation correctly follows a specification. But even with a provably correct implementation, given a choice, would a node choose to follow it? This paper explores how to create distributed system specifications that will be faithfully implemented in networks with rational nodes, so that no node will choose to deviate. Given a strategyproof centralized mechanism, and given a network of nodes modeled as having rational-manipulation faults, we provide a proof technique to establish the incentive-, communication-, and algorithm-compatibility properties that guarantee that participating nodes are faithful to a suggested specification. As a case study, we apply our methods to extend the strategyproof interdomain routing mechanism proposed by Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS) [7], defining a faithful implementation.
Published Version: doi:10.1145/1011767.1011781
Other Sources: http://www.eecs.harvard.edu/econcs/pubs/podc04.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search