Publication:
Specification Faithfulness in Networks with Rational Nodes

Thumbnail Image

Open/View Files

Primary Shneidman_Specification.pdf (185.05 KB)

Date

2004

Authors

Published Version

10.1145/1011767.1011781

Journal Title

Journal ISSN

Volume Title

Publisher

Association for Computing Machinery
The Harvard community has made this article openly available. Please share how this access benefits you.

Research Projects

Organizational Units

Journal Issue

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.

Research Data

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.

Description

Other Available Sources

http://www.eecs.harvard.edu/econcs/pubs/podc04.pdf

Keywords

algorithm compatibility, communication compatibility, computational mechanism design, distributed algorithmic mechanism design, failure models, incentive compatibility, rational failure, rational manipulation

Terms of Use

This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service

URI

http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443

Collections

FAS Scholarly Articles

Endorsement

Review

Supplemented By

Referenced By

Related Stories

Story
Specification Faithfulness in Networks with Rational… : DASH Story 2013-02-06
I need to research some information for my Diploma and since our library purchased some subscriptions the access from the university network is possible most of the times. But working late at night and researching from home very cumbersome. Open Access helps me finish my work, so thank you. Since I won't be a student for the rest of my life, it also helps to keep up with newer technologies and research after leaving the university and thus having no access to subscriptions to publications bought by the university's library.