Faithfulness in Internet Algorithms

DSpace/Manakin Repository

Faithfulness in Internet Algorithms

Show simple item record Shneidman, Jeffrey Parkes, David C. Massoulie, Laurent 2010-05-03T17:00:36Z 2004
dc.identifier.citation Shneidman, Jeffrey, David C. Parkes, and Laurent Massoulie. 2004. Faithfulness in internet algorithms. In Proceedings of the ACM SIGCOMM workshop on practice and theory of incentives in networked systems: September 3, 2004, Portland, Oregon, ed. D. Katabi, R. Sami, ACM Digital Library, Association for Computing Machinery, and Special Interest Group on Data Communications, 220-227. New York, N.Y.: ACM Press. en_US
dc.identifier.isbn 1-58113-942-9 en_US
dc.description.abstract Proving or disproving faithfulness (a property describing robustness to rational manipulation in action as well as information revelation) is an appealing goal when reasoning about distributed systems containing rational participants. Recent work formalizes the notion of faithfulness and its foundation properties, and presents a general proof technique in the course of proving the ex post Nash faithfulness of a theoretical routing problem [11].In this paper, we use a less formal approach and take some first steps in faithfulness analysis for existing algorithms running on the Internet. To this end, we consider the expected faithfulness of BitTorrent, a popular file download system, and show how manual backtracing (similar to the the ideas behind program slicing [22]) can be used to find rational manipulation problems. Although this primitive technique has serious drawbacks, it can be useful in disproving faithfulness.Building provably faithful Internet protocols and their corresponding specifications can be quite difficult depending on the system knowledge assumptions and problem complexity. We present some of the open problems that are associated with these challenges. en_US
dc.description.sponsorship Engineering and Applied Sciences en_US
dc.language.iso en_US en_US
dc.publisher Association for Computing Machinery en_US
dc.relation.isversionof doi:10.1145/1016527.1016537 en_US
dc.relation.hasversion en_US
dash.license LAA
dc.subject backtracing en_US
dc.subject computational failure models en_US
dc.subject computational mechanism design en_US
dc.subject distributed algorithmic mechanism design en_US
dc.subject faithfulness en_US
dc.subject program slicing en_US
dc.subject rational failure en_US
dc.subject rational manipulation en_US
dc.title Faithfulness in Internet Algorithms en_US
dc.type Other en_US
dc.description.version Accepted Manuscript en_US Parkes, David C. 2010-05-03T17:00:36Z

Files in this item

Files Size Format View
Shneidman_Faithfulness.pdf 312.1Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record


Search DASH

Advanced Search