Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)
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

Ort, förlag, år, upplaga, sidor
2015. , 115 s.
Serie
TRITA-ICT-EX, 2015:137
Nyckelord [en]
Byzantine Failures, Fault Tolerance, Performance, Reliability
Nationell ämneskategori
Programvaruteknik
Identifikatorer
URN: urn:nbn:se:kth:diva-170553OAI: oai:DiVA.org:kth-170553DiVA: diva2:838919
Utbildningsprogram
Teknologie masterexamen - Programvaruteknik för distribuerade system
Presentation
2015-06-23, Seminar room Grimeton at CoS, Electrum, elevator B, 4th floor, Isafjordsgatan 22, Kista, Stockholm, 13:22 (Engelska)
Handledare
Tillgänglig från: 2015-07-28 Skapad: 2015-07-01 Senast uppdaterad: 2017-06-16Bibliografiskt granskad

Open Access i DiVA

Thesis_Zeeshan_Abid_20150701-Final.pdf(1258 kB)520 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1258 kBChecksumma SHA-512
9dc986b8cceb60bd4e10acdabb0b80687169936ab6b5e6e68979f4ce712726d0229971eda9a878f1ff8591c2eb06112bb218cd93c36d2fd44c2b4247a4f9fb3b
Typ fulltextMimetyp application/pdf

Sök vidare i DiVA

Av författaren/redaktören
Abid, Muhammad Zeeshan
Av organisationen
Skolan för informations- och kommunikationsteknik (ICT)
Programvaruteknik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 520 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

Totalt: 566 träffar
RefereraExporteraLänk till posten
Permanent länk

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