Specification Faithfulness in Networks with Rational Nodes

• Published in: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing - PODC '04
• Main Authors: Shneidman, Jeffrey, Parkes, David C.
• Format: Other/Unknown Material
• Language: English
• Published: Association for Computing Machinery 2004
• Subjects: algorithm compatibility; communication compatibility; computational mechanism design; distributed algorithmic mechanism design; failure models; incentive compatibility; rational failure; rational manipulation; sami
• Online Access: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443; https://doi.org/10.1145/1011767.1011781

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. Engineering and Applied Sciences Accepted Manuscript