PDF Publication Title:
Text from PDF Page: 018
18 1.5. CONTRIBUTIONS 1.5 Contributions This thesis is divided into 8 chapters, over which we construct novel generalised algorithms for solving distributed consensus by progressively generalising the popular Paxos algorithm. Overall, we make the following key contributions: Chapter 2 We begin by defining the problem of distributed consensus and outline two known solutions, a simple straw-man algorithm and the widely used Paxos algorithm. We prove that both algorithms satisfy the necessary requirements to solve consensus. Chapter 3 In this systematisation of knowledge chapter, we outline the most common refinements to the Paxos algorithm, separating the underlying algorithmic contri- butions from the particulars of the framing and terminology used in the literature, which often differs greatly between publications. Chapter 4 We generalise the Paxos algorithm by weakening the quorum intersection requirements to permit non-intersecting quorums within each of the algorithm’s two phases. We then propose a further generalisation by weakening the quorum intersec- tion requirements to permit non-intersecting quorums between the algorithm’s first phase and subsequent second phases. Chapter 5 We prove that quorum intersection is transitive and can be reused, allowing in some scenarios decisions to be reached with fewer participants. Chapter 6 We generalise the Paxos algorithm by weakening the value selection rules by utilising knowledge from the algorithm’s first phase. This generalisation allows participants more flexibility when choosing a value to propose. Chapter 7 We further extend our generalisation permitting various mechanisms for the sharing of phases to best take advantage of the generalisation thus far. We present algorithms which provide new progress guarantees and can reach decisions in few phases. The result of this thesis is a family of approaches to achieving distributed consensus, which generalises over the most popular existing algorithms such as Paxos and Fast Paxos [Lam05a]. We aim to further understanding of this often poorly understood field and demonstrate the breadth of possible correct approaches to solving consensus. Later in the thesis, we explore the wide-reaching implications of our revised understanding of consensus. We focus on how to improve the performance and reliability of consensus al- gorithms and thus the distributed systems built on top of them. Distributed systems are famous for the need to compromise between desirable properties, largely due to popular formulations such as CAP theorem. However, such formulations are crude. In contrast, we aim to quantify the specific tradeoffs available for consensus and demonstrate algorithms which achieve these properties.PDF Image | Distributed consensus
PDF Search Title:
Distributed consensusOriginal File Name Searched:
UCAM-CL-TR-935.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)