Specification Faithfulness in Networks with Rational Nodes

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...

Full description

Bibliographic Details
Main Authors: Jeffrey Shneidman, David C. Parkes
Other Authors: The Pennsylvania State University CiteSeerX Archives
Format: Text
Language:English
Published: 2004
Subjects:
Algorithms
Design
Economics. Keywords Distributed Algorithmic Mechanism Design
Computational Mechanism Design
Rational Manipulation
Algorithm Compatibility
Communication Compatibility
Incentive Compatibility
Failure Models
Rational Failure
sami
Online Access:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3968
http://www.eecs.harvard.edu/econcs/bib/./cache/shneidman04.pdf
Description
Summary: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.

Similar Items