Byzantine Agreement by Distributed Randomization in 0(log N) Rounds

John H. ReifPaul G. Spirakis

Editore: Forgotten Books
Formato: PDF
Testo in en
Cloud: Scopri di più
Compatibilità: Tutti i dispositivi (eccetto Kindle) Scopri di più
Dimensioni: 364,71 KB
  • EAN: 9780243811069
pagabile con 18App pagabile con Carta del Docente

Articolo acquistabile con 18App e Carta del Docente

€ 5,85

Venduto e spedito da IBS

6 punti Premium

Scaricabile subito

Aggiungi al carrello Regala

non è possibile acquistare ebook su dispositivi Apple. Puoi comunque aggiungerli alla wishlist

The Byzantine Agreement (ba) problem is essentially the problem of finding a protocol for reaching agreement among n distributed processes of which at most t may be faulty. BA was defined by Pease, Shostak and Lamport [psl, 80] and is essential for maintaining coordination and synchronization among processes in distributed systems. [plf, 82] showed that the BA problem has no deterministic solution in the case the processes are asynchronous. [ds, 8l] showed that t+1 rounds are necessary for synchronous processgfifland deterministic potocols. Ben — Or [eo, 83] gave a randomized solqngflngthe asynchronous BA problem. However, his algorithm needsifiapl exponential number of messages and rounds for t for anxrgxzjgflgbut-requires a constant number of rounds and a polynomial numberfiof messages in the case t Rabin [r, introduced the assumption of a single random bit per round (which all processes can read) to solve the asynchronous BA problem, with no error, in an expected constant number of rounds and by using 0(n2) messages. He further observed that this message bound could be reduced to 0(nt) messages. Rabin also showed how to modify his algorithm to take only a fixed number R of rounds with reliability 1 — 2-r and by using the same number of messages. Apparently, the pre-dealt nature of the random sequence of bits required for Rabin's algorithm is crucial.