Faithfulness in internet algorithms

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.

REFERENCES

• 1: T. Anderson, S. Shenker, I. Stoica, and D. Wetherall. Design Guidelines for Robust Internet Protocols. HotNets-I, October 2002.
• 2: Blizzard Game Web site, World of Warcraft BitTorrent FAQ. http://www.blizzard.com/wow/faq/bittorrent.shtml.
• 3: Felix Brandt , Gerhard Weiß, Antisocial Agents and Vickrey Auctions, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.335-347, August 01-03, 2001
• 4: Bram Cohen. Incentives Build Robustness in BitTorrent. In Workshop on Economics of Peer to Peer Systems, June 2003.
• 5: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 6: Dawson Engler and Madanlal Musuvathi. Model-checking large network protocol implementations. In To appear in NSDI 2004, 2004.
• 7: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 8: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 9: Info-Anarchy Web site, definition for Parallel Downloading Systems: Hive. http://www.infoanarchy.org/wiki/wiki.pl?hive.
• 10: Jeffrey Shneidman and David C. Parkes. Rationality and Self-Interest in Peer to Peer Networks. In 2nd Int. Workshop on Peer-to-Peer Systems (IPTPS'03), 2003.
• 11: Jeffrey Shneidman , David C. Parkes, Specification faithfulness in networks with rational nodes, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011781]
• 12: Lindows Web site, Press Release about BitTorrent. http://www.linspire.com/lindows_news_pressreleases_archives.php?id=111.
• 13: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 14: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 15: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 16: Noam Nisan and Amir Ronen. Algorithmic Mechanism Design. Games and Economic Behavior, 35:166--196, 2001.
• 17: David Christopher Parkes , Lyle H. Ungar, Iterative combinatorial auctions: achieving economic and computational efficiency, 2001
• 18: Pablo Rodriguez. Scalable Content Distribution in the Internet. PhD thesis, Federal Institut of Technology, Lausanne (EPFL), Sept 2000.
• 19: Stefan Savage , Neal Cardwell , David Wetherall , Tom Anderson, TCP congestion control with a misbehaving receiver, ACM SIGCOMM Computer Communication Review, v.29 n.5, October 1999 [doi>10.1145/505696.505704]
• 20: Stefan Savage. Private Communication, 4/2004.
• 21: F. Tip. A survey of program slicing techniques. Journal of programming languages, 3:121--189, 1995.
• 22: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Design, Economics

Keywords:
backtracing, computational failure models, computational mechanism design, distributed algorithmic mechanism design, faithfulness, program slicing, rational failure, rational manipulation