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...
Main Authors: | , |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Published: |
2004
|
Subjects: | |
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 |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.2.3968 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.2.3968 2023-05-15T18:12:06+02:00 Specification Faithfulness in Networks with Rational Nodes Jeffrey Shneidman David C. Parkes The Pennsylvania State University CiteSeerX Archives 2004 application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3968 http://www.eecs.harvard.edu/econcs/bib/./cache/shneidman04.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3968 http://www.eecs.harvard.edu/econcs/bib/./cache/shneidman04.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://www.eecs.harvard.edu/econcs/bib/./cache/shneidman04.pdf Algorithms Design Economics. Keywords Distributed Algorithmic Mechanism Design Computational Mechanism Design Rational Manipulation Algorithm Compatibility Communication Compatibility Incentive Compatibility Failure Models Rational Failure text 2004 ftciteseerx 2016-01-07T17:18:27Z 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. Text sami Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
topic |
Algorithms Design Economics. Keywords Distributed Algorithmic Mechanism Design Computational Mechanism Design Rational Manipulation Algorithm Compatibility Communication Compatibility Incentive Compatibility Failure Models Rational Failure |
spellingShingle |
Algorithms Design Economics. Keywords Distributed Algorithmic Mechanism Design Computational Mechanism Design Rational Manipulation Algorithm Compatibility Communication Compatibility Incentive Compatibility Failure Models Rational Failure Jeffrey Shneidman David C. Parkes Specification Faithfulness in Networks with Rational Nodes |
topic_facet |
Algorithms Design Economics. Keywords Distributed Algorithmic Mechanism Design Computational Mechanism Design Rational Manipulation Algorithm Compatibility Communication Compatibility Incentive Compatibility Failure Models Rational Failure |
description |
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. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Jeffrey Shneidman David C. Parkes |
author_facet |
Jeffrey Shneidman David C. Parkes |
author_sort |
Jeffrey Shneidman |
title |
Specification Faithfulness in Networks with Rational Nodes |
title_short |
Specification Faithfulness in Networks with Rational Nodes |
title_full |
Specification Faithfulness in Networks with Rational Nodes |
title_fullStr |
Specification Faithfulness in Networks with Rational Nodes |
title_full_unstemmed |
Specification Faithfulness in Networks with Rational Nodes |
title_sort |
specification faithfulness in networks with rational nodes |
publishDate |
2004 |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3968 http://www.eecs.harvard.edu/econcs/bib/./cache/shneidman04.pdf |
genre |
sami |
genre_facet |
sami |
op_source |
http://www.eecs.harvard.edu/econcs/bib/./cache/shneidman04.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3968 http://www.eecs.harvard.edu/econcs/bib/./cache/shneidman04.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766184661012185088 |