000169619 001__ 169619
000169619 005__ 20190619003311.0
000169619 0247_ $$2doi$$a10.5075/epfl-thesis-5242
000169619 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis5242-9
000169619 02471 $$2nebis$$a6665729
000169619 037__ $$aTHESIS
000169619 041__ $$aeng
000169619 088__ $$a5242
000169619 245__ $$aA High-Throughput Byzantine Fault-Tolerant Protocol
000169619 269__ $$a2012
000169619 260__ $$bEPFL$$c2012$$aLausanne
000169619 300__ $$a163
000169619 336__ $$aTheses
000169619 520__ $$aState-machine replication (SMR) is a software technique  for tolerating failures and for providing high availability  in large-scale systems, through the use of commodity  hardware. A replicated state-machine comprises a number of  replicas, each of which runs an agreement protocol, with the  goal of ensuring a consistent state across all of the  replicas. In hostile environments, such as the Internet,  Byzantine fault tolerant state-machine replication (BFT) is  an important technique for providing robust services. During  the past decade, we have seen an emergence of various BFT  protocols. In order to be adopted, besides providing  correctness, a BFT must provide good performance as well.  Consequently, all of the new protocols focus on improving  performance under various conditions. However, a closer look at the performance of  state-of-the-art BFT protocols reveals that even in best-case  execution scenarios, they still remain far behind their  theoretical maximum. Based on exhaustive evaluation and  monitoring of existing BFT protocols, we highlight a few  impediments to their scalability. These obstructions include  the use of IP multicast, the presence of bottlenecks due to  asymmetric replica processing, and an unbalanced network  bandwidth utilization. The goal of this thesis is to evaluate the actual impact  of these scalability impediments, and to offer a solution for  a high-throughput BFT protocol in the case in which the  network itself is the bottleneck. To that end, we have  developed Ring, a new BFT protocol which circumvents the  aforementioned impediments. As its name suggests, Ring uses  the ring communication topology, in the fault-free case. In  the ring topology, each replica only performs point-to-point  communications with two other replicas, namely its neighbors  on the ring. Moreover, all of the replicas equally accept  requests from clients and perform symmetric processing. Our  performance evaluation shows that, with the network as the  bottleneck, Ring outperforms all other, state-of-the-art BFT  protocols. Ring achieves 118 Mbps on the Fast Ethernet –  a 24% improvement in throughput over previous protocols. Finally, we conducted an extensive practical and analytic  evaluation of Ring. In order to analyse benefits (and  drawbacks) of Ring (and other protocols) under different  settings, without resorting to costly experimentation, we  developed an analytical performance model. Our performance  model is based on queueing theory, and relies only on a  handful of protocolagnostic measurements of the  environment.
000169619 6531_ $$aalgorithms
000169619 6531_ $$aByzantine fault tolerance
000169619 6531_ $$aasynchronous systems
000169619 6531_ $$ascalability
000169619 6531_ $$ahigh throughput
000169619 6531_ $$acorrectness proofs
000169619 6531_ $$aperformance
000169619 6531_ $$aring topology
000169619 6531_ $$aanalytic modelling
000169619 6531_ $$aqueueing theory
000169619 6531_ $$areplication and security
000169619 6531_ $$aalgorithmes
000169619 6531_ $$afautes Byzantines
000169619 6531_ $$asystèmes asynchrones
000169619 6531_ $$aévolutivité
000169619 6531_ $$ahaut débit
000169619 6531_ $$apreuves de protocoles
000169619 6531_ $$aperformance
000169619 6531_ $$atopologie en anneau
000169619 6531_ $$amodèles analytiques
000169619 6531_ $$athéorie des files d'attente
000169619 6531_ $$aréplication
000169619 6531_ $$asécurité
000169619 700__ $$0242989$$g173379$$aKnezevic, Nikola
000169619 720_2 $$aGuerraoui, Rachid$$edir.$$g105326$$0240335
000169619 8564_ $$uhttps://infoscience.epfl.ch/record/169619/files/EPFL_TH5242.pdf$$zTexte intégral / Full text$$s2138632$$yTexte intégral / Full text
000169619 909C0 $$xU10407$$0252114$$pDCL
000169619 909CO $$pthesis-public$$pDOI$$pIC$$ooai:infoscience.tind.io:169619$$qGLOBAL_SET$$pthesis$$pthesis-bn2018$$qDOI2
000169619 918__ $$dEDIC2005-2015$$cIIF$$aIC
000169619 919__ $$aLPD
000169619 920__ $$b2012
000169619 970__ $$a5242/THESES
000169619 973__ $$sPUBLISHED$$aEPFL
000169619 980__ $$aTHESIS