On the impact of link faults on Byzantine agreement

Agreement problems and their solutions are essential to fault-tolerant distributed computing. Over the years, different assumptions on failures have been considered, but most of these assumptions were focusing on either processes or links. In contrast, we examine a model where both links and processes can fail. In this model we devise a unified lower bound for resilience to both classes of faults. We show that the bound is tight by devising a simple retransmission scheme that allows optimally resilient algorithms to be constructed from well known algorithms by transparently adding link-fault tolerance. Our results show that when considering multiple independent failure modes, resilience bounds are not necessarily additive. (C) 2014 Elsevier Inc. All rights reserved.


Published in:
Information And Computation, 239, 170-181
Year:
2014
Publisher:
San Diego, Academic Press Inc Elsevier Science
ISSN:
0890-5401
Keywords:
Note:
6th International Conference on Language and Automata Theory and Applications (LATA), A Coruna, SPAIN, MAR 05-09, 2012
Laboratories:




 Record created 2015-02-20, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)