Utilize este identificador para referenciar este registo: http://hdl.handle.net/10451/14134
Título: Asynchronous Byzantine Consensus with 2f+1 Processes (extended version)
Autor: Correia, Miguel
Veronese, Giuliana Santos
Lung, Lau Cheuk
Data: 29-Dez-2009
Relatório da Série N.º: 2009-17
Resumo: Byzantine consensus in asynchronous message-passing systems has been shown to require at least $3f+1$ processes to be solvable in several system models (e.g., with failure detectors, partial synchrony or randomization). Recently a couple of solutions to implement Byzantine fault-tolerant state-machine replication using only $2f+1$ replicas have appeared. This reduction from $3f+1$ to $2f+1$ is possible with a hybrid system model, i.e., by extending the system model with trusted/trustworthy components that constrain the power of faulty processes to have certain behaviors. Despite these important results, the problem of solving Byzantine consensus with only $2f+1$ processes is still far from being well understood. In this paper we present a methodology to transform crash consensus algorithms into Byzantine consensus algorithms with different characteristics, with the assistance of a reliable broadcast primitive that requires trusted/trustworthy components to be implemented. We exemplify the methodology with two algorithms, one that uses failure detectors and one that is randomized. We also define a new flavor of consensus and use it to solve atomic broadcast with only $2f+1$ processes, showing the practical interest of the consensus algorithms presented.
Descrição: Reviewed by Paulo J. Sousa
URI: http://hdl.handle.net/10451/14134
Aparece nas colecções:FC-DI - Technical Reports

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
09-17.pdf474,61 kBAdobe PDFVer/Abrir

FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.