Faithfulness in Internet Algorithms

DSpace/Manakin Repository

Faithfulness in Internet Algorithms

Citable link to this page

. . . . . .

Title: Faithfulness in Internet Algorithms
Author: Shneidman, Jeffrey; Parkes, David C.; Massoulie, Laurent

Note: Order does not necessarily reflect citation order of authors.

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. http://portal.acm.org/toc.cfm?id=1016527.
Full Text & Related Files:
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.
Published Version: doi:10.1145/1016527.1016537
Other Sources: http://www.eecs.harvard.edu/econcs/pubs/pins04.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4045846

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7501]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters