Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A Multi-leader Approach to Byzantine Fault Tolerance: Achieving Higher Throughput Using Concurrent Consensus
KTH, Skolan för informations- och kommunikationsteknik (ICT). Technische Universität Braunschweig.
2015 (engelsk)Independent thesis Advanced level (degree of Master (Two Years)), 20 poäng / 30 hpOppgave
Abstract [en]

Byzantine Fault Tolerant protocols are complicated and hard to implement.Today’s software industry is reluctant to adopt these protocols because of thehigh overhead of message exchange in the agreement phase and the high resourceconsumption necessary to tolerate faults (as 3 f + 1 replicas are required totolerate f faults). Moreover, total ordering of messages is needed by mostclassical protocols to provide strong consistency in both agreement and executionphases. Research has improved throughput of the execution phase by introducingconcurrency using modern multicore infrastructures in recent years. However,improvements to the agreement phase remains an open area.

Byzantine Fault Tolerant systems use State Machine Replication to tolerate awide range of faults. The approach uses leader based consensus algorithms for thedeterministic execution of service on all replicas to make sure all correct replicasreach same state. For this purpose, several algorithms have been proposed toprovide total ordering of messages through an elected leader. Usually, a singleleader is considered to be a bottleneck as it cannot provide the desired throughputfor real-time software services. In order to achieve a higher throughput there is aneed for a solution which can execute multiple consensus rounds concurrently.

We present a solution that enables multiple consensus rounds in parallel bychoosing multiple leaders. By enabling concurrent consensus, our approach canexecute several requests in parallel. In our approach we incorporate applicationspecific knowledge to split the total order of events into multiple partial orderswhich are causally consistent in order to ensure safety. Furthermore, a dependencycheck is required for every client request before it is assigned to a particular leaderfor agreement. This methodology relies on optimistic prediction of dependenciesto provide higher throughput. We also propose a solution to correct the course ofexecution without rollbacking if dependencies were wrongly predicted.

Our evaluation shows that in normal cases this approach can achieve upto 100% higher throughput than conventional approaches for large numbers ofclients. We also show that this approach has the potential to perform better incomplex scenarios

sted, utgiver, år, opplag, sider
2015. , s. 115
Serie
TRITA-ICT-EX ; 2015:137
Emneord [en]
Byzantine Failures, Fault Tolerance, Performance, Reliability
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-170553OAI: oai:DiVA.org:kth-170553DiVA, id: diva2:838919
Utdanningsprogram
Master of Science - Software Engineering of Distributed Systems
Presentation
2015-06-23, Seminar room Grimeton at CoS, Electrum, elevator B, 4th floor, Isafjordsgatan 22, Kista, Stockholm, 13:22 (engelsk)
Veileder
Tilgjengelig fra: 2015-07-28 Laget: 2015-07-01 Sist oppdatert: 2018-01-11bibliografisk kontrollert

Open Access i DiVA

Thesis_Zeeshan_Abid_20150701-Final.pdf(1258 kB)932 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1258 kBChecksum SHA-512
9dc986b8cceb60bd4e10acdabb0b80687169936ab6b5e6e68979f4ce712726d0229971eda9a878f1ff8591c2eb06112bb218cd93c36d2fd44c2b4247a4f9fb3b
Type fulltextMimetype application/pdf

Søk i DiVA

Av forfatter/redaktør
Abid, Muhammad Zeeshan
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 932 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 1274 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf