PDF Publication Title:
Text from PDF Page: 017
CHAPTER 1. INTRODUCTION 17 they are often correlated and escalated by one another. In practice, deploying Paxos does not guarantee availability since the algorithm’s progress depends on satisfying synchrony and liveness conditions which cannot be guaranteed by today’s systems. Paxos’s approach to consensus establishes one participant as the leader and makes that participant responsible for decisions. This centralised approach provides simplicity as a single point of serialisation yet it also bottlenecks the algorithm’s performance to that of a single highly congested participant. Since the leader is responsible for decision making, all requests for decisions must be forwarded to and handled by the leader, further increasing decision latency. The leader introduces a single point of failure in the distributed system. Whilst Paxos is able to recover from leader failure under given conditions, such a recovery may be slow and cumbersome and usually results in a period of unavailability. The limitations are widely known, yet few alternatives to Paxos are utilised in practice. The vast academic literature in distributed consensus generally focuses on mitigating these lim- itations though optimisation, extension and pragmatic implementation. Given the limita- tions we have discussed thus far, production systems such as Amazon’s Dynamo [DHJ+07] and Facebook’s TAO [BAC+13, LVA+15] opt to sacrifice strong consistency guarantees in favour of high availability. 1.4 Approach The question naturally arises of whether these limitations are inherent to the problem of consensus or specific to the approach taken by the Paxos algorithm? Likewise, is the Paxos algorithm the optimal solution to consensus? These are the questions which will guide our research. Our approach is to re-examine the problem of distributed consensus and how we as a com- munity approach it. In contrast to previous work, we undertake an extensive examination of how to achieve consensus over a single value. Due to the wide spread adoption of Paxos and our focus on the underlying theory of consensus, the results of our analysis could have wide-reaching implications, which are agnostic (thus not limited in scope) to particular systems, hardware, workloads or deployment scenarios. We begin by developing a framework for proving the correctness of a consensus algorithm and apply it to the Paxos algorithm. The purpose of the framework is to be explicit about how the properties of the algorithm are used within the proof of correctness. This allows us to modify the algorithm and verify correctness without re-proving the whole algorithm. The surprising results of this approach are twofold: firstly, the proof of correctness did not use the full strength of the properties provided and secondly, there are many approaches which satisfy the same properties. These observations formed the basis of our progressive generalisation of the Paxos algorithm. At each stage, we were able to verify correctness by building upon the original proof.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 | RSS | AMP |