Loading...
Please wait, while we are loading the content...
Similar Documents
Faithfulness in internet algorithms
| Content Provider | ACM Digital Library |
|---|---|
| Author | Shneidman, Jeffrey Parkes, David C. Massoulié, Laurent |
| 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. |
| Starting Page | 220 |
| Ending Page | 227 |
| Page Count | 8 |
| File Format | |
| ISBN | 158113942X |
| DOI | 10.1145/1016527.1016537 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2004-09-03 |
| Publisher Place | New York |
| Access Restriction | Subscribed |
| Subject Keyword | Rational failure Program slicing Backtracing Computational failure models Rational manipulation Distributed algorithmic mechanism design Faithfulness Computational mechanism design |
| Content Type | Text |
| Resource Type | Article |
