PDF Publication Title:
Text from PDF Page: 014
14 1.1. STATE OF THE ART 1.1 State of the art The ability to reach an agreement between parties is a fundamental necessity of modern society, whether it is deciding a time for a meeting or whom will govern a country. The same is true for distributed computer systems where agreement is necessary for hosts to share consistent state for vital functions such as addressing, resource allocation, file systems, primary election, routing, locking, ordering and coordination. Agreement covers a broad spectrum of decision problems in distributed systems. Dis- tributed consensus is one such problem which is characterised by two guarantees: firstly that all decisions are final, without assuming reliability or synchrony (safety guarantee) and secondly that eventually a decision will be reached (progress guarantee). It is known to be impossible to guarantee progress without making assumptions regarding synchrony or reliability [FLP85]. Therefore, algorithms which solve consensus aim to guarantee progress under the weakest liveness assumptions possible. The Paxos algorithm, originally proposed by Leslie Lamport in 1998 [Lam98] and later refined [Lam01a], is at the heart of how we achieve distributed consensus today1. Broadly speaking, its approach operates in two stages, each requiring agreement by the majority of participants. The first stage establishes one of the participants as the leader, preventing past leaders from making any further decisions. Once the majority of participants have agreed on who will lead, the leader proceeds to the second stage where decisions are made by getting the backing of the majority of participants. The leader is responsible for ensuring that all past decisions, learned during the first stage of the algorithm, are preserved and only proposes new values if it is safe to do so. This algorithm is guaranteed to reach a decision provided that at least a majority of participants are up and communicating synchronously. This approach is now widely adopted as the foundation of many production systems. 1.2 Historical background The problem of distributed consensus emerged in the academic literature in the early 1980s. Originally, distributed consensus was a generalisation of a widely studied transac- tion commit problem from the field of distributed databases. Somewhat surprisingly, the problem of distributed consensus was popularised by a proof of its impossibility. Fischer, Lynch and Paterson [FLP85] demonstrated in 1985 that it is not possible for any dis- tributed consensus algorithm to guarantee termination in an asynchronous system where participants may fail. The proof is notable for the surprisingly strong model under which 1For now, we use the term Paxos to refer to the algorithm as it is commonly used today, instead of as it was first described by Lamport. Often the term Multi-degree Paxos or just Multi-Paxos is used for this purpose.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)