Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
BAR Primer

A. Clement, H. Li, J. Napper, JP. Martin, L. Alvisi, and M. Dahlin

Abstract

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.

Details

Publication typeInproceedings
Published inProc. DSN-2008
Pages287-296
PublisherIEEE Computer Society
> Publications > BAR Primer