A. Clement, H. Li, J. Napper, JP. Martin, L. Alvisi, and M. Dahlin
Byzantine and rational behaviors are increasingly recognized as unavoidable realities in today’s cooperative services. Yet, how to design BAR-tolerant protocols and rigorously prove them strategy proof remains somewhat of a mystery: existing examples tend either to focus on unrealistically simple problems or to want in rigor. The goal of this paper is to demystify the process by presenting the full algorithmic development cycle that, starting from the classic synchronous Repeated Terminating Reliable Broadcast (RTRB) problem statement, leads to a provably BAR-tolerant solution. We i) express R-TRB as a game; ii) why the strategy corresponding to the optimal Byzantine Fault Tolerant algorithm of Dolev and Strong does not guarantee safety when non-Byzantine players behave selfishly; iii) how to derive a BAR-tolerant R-TRB protocol: iv) how to prove rigorously that the protocol ensures safety in the presence of non-Byzantine selfish players.
In Proc. DSN-2008
Publisher IEEE Computer Society
Copyright © 2007 IEEE. Reprinted from IEEE Computer Society. This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to firstname.lastname@example.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.