Edmund L. Wong, Allen Clement, Isaac Levy, Lorenzo Alvisi, and Mike Dahlin

Proceedings of the International Conference On Principles Of Distributed Systems (OPODIS) 2011.

View PDF or BibTeX.

areas
Distributed Systems, Game Theory

abstract
Cooperative, peer-to-peer (P2P) services—distributed systems consisting of participants from multiple administrative domains (MAD)—must deal with the threat of arbitrary (Byzantine) failures while incentivizing the cooperation of potentially selfish (rational) nodes that such services rely on to function. This paper investigates how to specify conditions (i.e., a solution concept) for rational cooperation in an environment that also contains Byzantine and obedient peers. We find that regret-free approaches—which, inspired by traditional Byzantine fault tolerance, condition rational cooperation on identifying a strategy that proves a best response regardless of how Byzantine failures occur—are unattainable in many fault-tolerant distributed systems. We suggest an alternative regret-braving approach, in which rational nodes aim to best respond to their expectations regarding Byzantine failures: the chosen strategy guarantees no regret only to the extent that such expectations prove correct. While work on regret-braving solution concepts is just beginning, our preliminary results show that these solution concepts are not subject to the fundamental limitations inherent to regret freedom.