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...
Published in: | Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing - PODC '04 |
---|---|
Main Authors: | , |
Format: | Other/Unknown Material |
Language: | English |
Published: |
Association for Computing Machinery
2004
|
Subjects: | |
Online Access: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443 https://doi.org/10.1145/1011767.1011781 |
id |
ftharvardudash:oai:dash.harvard.edu:1/4054443 |
---|---|
record_format |
openpolar |
spelling |
ftharvardudash:oai:dash.harvard.edu:1/4054443 2023-05-15T18:12:07+02:00 Specification Faithfulness in Networks with Rational Nodes Shneidman, Jeffrey Parkes, David C. 2004 application/pdf http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443 https://doi.org/10.1145/1011767.1011781 en_US eng Association for Computing Machinery doi:10.1145/1011767.1011781 http://www.eecs.harvard.edu/econcs/pubs/podc04.pdf 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. 1-58113-802-4 9781581138023 http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443 algorithm compatibility communication compatibility computational mechanism design distributed algorithmic mechanism design failure models incentive compatibility rational failure rational manipulation Monograph or Book 2004 ftharvardudash https://doi.org/10.1145/1011767.1011781 2022-04-04T12:42:31Z 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 Other/Unknown Material sami Harvard University: DASH - Digital Access to Scholarship at Harvard Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing - PODC '04 88 |
institution |
Open Polar |
collection |
Harvard University: DASH - Digital Access to Scholarship at Harvard |
op_collection_id |
ftharvardudash |
language |
English |
topic |
algorithm compatibility communication compatibility computational mechanism design distributed algorithmic mechanism design failure models incentive compatibility rational failure rational manipulation |
spellingShingle |
algorithm compatibility communication compatibility computational mechanism design distributed algorithmic mechanism design failure models incentive compatibility rational failure rational manipulation Shneidman, Jeffrey Parkes, David C. Specification Faithfulness in Networks with Rational Nodes |
topic_facet |
algorithm compatibility communication compatibility computational mechanism design distributed algorithmic mechanism design failure models incentive compatibility rational failure rational manipulation |
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. Engineering and Applied Sciences Accepted Manuscript |
format |
Other/Unknown Material |
author |
Shneidman, Jeffrey Parkes, David C. |
author_facet |
Shneidman, Jeffrey Parkes, David C. |
author_sort |
Shneidman, Jeffrey |
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 |
publisher |
Association for Computing Machinery |
publishDate |
2004 |
url |
http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443 https://doi.org/10.1145/1011767.1011781 |
genre |
sami |
genre_facet |
sami |
op_relation |
doi:10.1145/1011767.1011781 http://www.eecs.harvard.edu/econcs/pubs/podc04.pdf 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. 1-58113-802-4 9781581138023 http://nrs.harvard.edu/urn-3:HUL.InstRepos:4054443 |
op_doi |
https://doi.org/10.1145/1011767.1011781 |
container_title |
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing - PODC '04 |
container_start_page |
88 |
_version_ |
1766184678152208384 |