BAR Primer

被引:9
作者
Clement, Allen [1 ]
Li, Harry [1 ]
Napper, Jeff [1 ]
Martin, Jean-Philippe [2 ]
Alvisi, Lorenzo [1 ]
Dahlin, Mike [1 ]
机构
[1] Univ Texas Austin, Austin, TX 78712 USA
[2] Microsoft Res Cambridge, Cambridge, England
来源
2008 IEEE INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS & NETWORKS WITH FTCS & DCC | 2008年
关键词
D O I
10.1109/DSN.2008.4630097
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 [计算机科学与技术];
摘要
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 (R-TRB) problem statement, leads to a provably BAR-tolerant solution. We show i) how to 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 rationally; 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 rational players.
引用
收藏
页码:287 / +
页数:2
相关论文
共 17 条
[1]
ABRAHAM I, 2006, P 25 PODC JUL
[2]
ADAR E, 2000, 1 MONDAY, V5, P2
[3]
AIYER AS, 2005, P 20 SOSP OCT
[4]
[Anonymous], 2003, PROC IPTPS
[5]
[Anonymous], P 23 S PRINC DISTR C
[6]
CLEMENT A, 2005, R0663 U TEX DEP COMP
[7]
AUTHENTICATED ALGORITHMS FOR BYZANTINE AGREEMENT [J].
DOLEV, D ;
STRONG, HR .
SIAM JOURNAL ON COMPUTING, 1983, 12 (04) :656-666
[8]
Fault tolerant implementation [J].
Eliaz, K .
REVIEW OF ECONOMIC STUDIES, 2002, 69 (03) :589-610
[9]
TRAGEDY OF COMMONS [J].
HARDIN, G .
SCIENCE, 1968, 162 (3859) :1243-+
[10]
Lamport L., 1982, ACM T PROGRAM LANG S