Random Notes
  • Introduction
  • Reading list
  • Theory
    • Index
      • Impossibility of Distributed Consensus with One Faulty Process
      • Time, Clocks, and the Ordering of Events in a Distributed System
      • Using Reasoning About Knowledge to analyze Distributed Systems
      • CAP Twelve Years Later: How the “Rules” Have Changed
      • A Note on Distributed Computing
  • Operating System
    • Index
  • Storage
    • Index
      • Tachyon: Reliable, Memory Speed Storage for Cluster Computing Frameworks
      • Exploiting Commutativity For Practical Fast Replication
      • Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
      • Building Consistent Transactions with Inconsistent Replication
      • Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System
      • Spanner: Google's Globally-Distributed Database
      • Bigtable: A Distributed Storage System for Structured Data
      • The Google File System
      • Dynamo: Amazon’s Highly Available Key-value Store
      • Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
      • Replicated Data Consistency Explained Through Baseball
      • Session Guarantees for Weakly Consistent Replicated Data
      • Flat Datacenter Storage
      • Small Cache, Big Effect: Provable Load Balancing forRandomly Partitioned Cluster Services
      • DistCache: provable load balancing for large-scale storage systems with distributed caching
      • Short Summaries
  • Coordination
    • Index
      • Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
      • Paxos made simple
      • ZooKeeper: Wait-free coordination for Internet-scale systems
      • Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering
      • Keeping CALM: When Distributed Consistency is Easy
      • In Search of an Understandable Consensus Algorithm
      • A comprehensive study of Convergent and Commutative Replicated Data Types
  • Fault Tolerance
    • Index
      • The Mystery Machine: End-to-end Performance Analysis of Large-scale Internet Services
      • Gray Failure: The Achilles’ Heel of Cloud-Scale Systems
      • Capturing and Enhancing In Situ System Observability for Failure Detection
      • Check before You Change: Preventing Correlated Failures in Service Updates
      • Efficient Scalable Thread-Safety-Violation Detection
      • REPT: Reverse Debugging of Failures in Deployed Software
      • Redundancy Does Not Imply Fault Tolerance
      • Fixed It For You:Protocol Repair Using Lineage Graphs
      • The Good, the Bad, and the Differences: Better Network Diagnostics with Differential Provenance
      • Lineage-driven Fault Injection
      • Short Summaries
  • Cloud Computing
    • Index
      • Improving MapReduce Performance in Heterogeneous Environments
      • CLARINET: WAN-Aware Optimization for Analytics Queries
      • MapReduce: Simplified Data Processing on Large Clusters
      • Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks
      • Resource Management
      • Apache Hadoop YARN: Yet Another Resource Negotiator
      • Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center
      • Dominant Resource Fairness: Fair Allocation of Multiple Resource Types
      • Large-scale cluster management at Google with Borg
      • MapReduce Online
      • Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling
      • Reining in the Outliers in Map-Reduce Clusters using Mantri
      • Effective Straggler Mitigation: Attack of the Clones
      • Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
      • Discretized Streams: Fault-Tolerant Streaming Computation at Scale
      • Sparrow: Distributed, Low Latency Scheduling
      • Making Sense of Performance in Data Analytics Framework
      • Monotasks: Architecting for Performance Clarity in Data Analytics Frameworks
      • Drizzle: Fast and Adaptable Stream Processing at Scale
      • Naiad: A Timely Dataflow System
      • The Dataflow Model:A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale
      • Interruptible Tasks:Treating Memory Pressure AsInterrupts for Highly Scalable Data-Parallel Program
      • PACMan: Coordinated Memory Caching for Parallel Jobs
      • Multi-Resource Packing for Cluster Schedulers
      • Other interesting papers
  • Systems for ML
    • Index
      • A Berkeley View of Systems Challenges for AI
      • Tiresias: A GPU Cluster Managerfor Distributed Deep Learning
      • Gandiva: Introspective Cluster Scheduling for Deep Learning
      • Workshop papers
      • Hidden Technical Debt in Machine Learning Systems
      • Inference Systems
      • Parameter Servers and AllReduce
      • Federated Learning at Scale - Part I
      • Federated Learning at Scale - Part II
      • Learning From Non-IID data
      • Ray: A Distributed Framework for Emerging AI Applications
      • PipeDream: Generalized Pipeline Parallelism for DNN Training
      • DeepXplore: Automated Whitebox Testingof Deep Learning Systems
      • Distributed Machine Learning Misc.
  • ML for Systems
    • Index
      • Short Summaries
  • Machine Learning
    • Index
      • Deep Learning with Differential Privacy
      • Accelerating Deep Learning via Importance Sampling
      • A Few Useful Things to Know About Machine Learning
  • Video Analytics
    • Index
      • Scaling Video Analytics on Constrained Edge Nodes
      • Focus: Querying Large Video Datasets with Low Latency and Low Cost
      • NoScope: Optimizing Neural Network Queriesover Video at Scale
      • Live Video Analytics at Scale with Approximation and Delay-Tolerance
      • Chameleon: Scalable Adaptation of Video Analytics
      • End-to-end Learning of Action Detection from Frame Glimpses in Videos
      • Short Summaries
  • Networking
    • Index
      • Salsify: Low-Latency Network Video through Tighter Integration between a Video Codec and a Transport
      • Learning in situ: a randomized experiment in video streaming
      • Short Summaries
  • Serverless
    • Index
      • Serverless Computing: One Step Forward, Two Steps Back
      • Encoding, Fast and Slow: Low-Latency Video Processing Using Thousands of Tiny Threads
      • SAND: Towards High-Performance Serverless Computing
      • Pocket: Elastic Ephemeral Storage for Serverless Analytics
      • Fault-tolerant and Transactional Stateful Serverless Workflows
  • Resource Disaggregation
    • Index
  • Edge Computing
    • Index
  • Security/Privacy
    • Index
      • Differential Privacy
      • Honeycrisp: Large-Scale Differentially Private Aggregation Without a Trusted Core
      • Short Summaries
  • Misc.
    • Index
      • Rate Limiting
      • Load Balancing
      • Consistency Models in Distributed System
      • Managing Complexity
      • System Design
      • Deep Dive into the Spark Scheduler
      • The Actor Model
      • Python Global Interpreter Lock
      • About Research and PhD
Powered by GitBook
On this page
  • TL;DR:
  • Summary:
  • Paxos Algorithm:
  • Question:
  • Related Links:

Was this helpful?

  1. Coordination
  2. Index

Paxos made simple

https://www.microsoft.com/en-us/research/uploads/prod/2016/12/paxos-simple-Copy.pdf

TL;DR:

Paxos is a protocol that solves the problem that getting a group of nodes to agree or reach consensus on a single value.

Summary:

In this paper, the author introduces Paxos, which is a fault-tolerant algorithm used to reach consensus among a collection of computers in asynchronous and non-Byzantine model.

The problem of consensus is to get a collection of computers to decide a thing as if they were one computer. The main difference between consensus and other agreement problems is that consensus protocols need to be fault tolerant, which means there is no single point of failure. In contrast, in protocols like Two-Phase commit, if the coordinator were to crash, the whole system might not able to make any progress. If there is a stable leader, consensus becomes trivial, because the leader can establish a total order over all operations itself and have other nodes follow it. However, the failure of the leader will prevent the system from making any progress. Moreover, if the leader election algorithm fails(which is likely to happen in case of network partition), there might exist multiple leaders and violates agreement property.

The paper defines three classes of agents:

1.Proposers(nodes that propose value) 2.Acceptors(remember the proposed values) 3.Learners(discover the chosen values).

Then, it describes the following failed attempts to solve consensus:

1.Single acceptor agent(act as a leader). Unsatisfactory because of the single point of failure. 2.Multiple acceptor agents. -acceptors accept the first value they receive -a value is chosen if it is accepted by a majority acceptors Unsatisfactory because we can easily construct cases in which no value is accepted by a majority of accepts, violating termination. 3. Accept more than one values Unsatisfactory because the message may be delivered out of order, violating agreement.

Paxos Algorithm:

Prepare Phase:

For proposer, it selects a new proposal number n and broadcast a prepare request(includes n) to acceptors. For acceptor, it compares n with the accepted proposal with the highest number. If n is greater, the acceptor sends back a promise to follow that proposer and the highest numbered proposal(and the value associated with the proposal) it has accepted, if any.

Accept Phase:

After the proposer receives responses from a majority of acceptors, the proposer will send an accept request to all acceptors. The accept message contains the proposal number and a value(the value of the highest numbered proposal or any value if all acceptors respond none) When an acceptor receives an accept request, it will accept the request if the proposal number is greater than or equal to the highest numbered proposal it has accepted. Finally, if an accept request is accepted by a majority of acceptors. The proposal is chosen(or decided).

Note: 1.The acceptor must remember the highest numbered proposal it has accepted if any even if it fails and recovers. The proposer can forget about its proposals as long as it never tries to issue another proposal with the same proposal number 2.The proposal number needs to be globally unique and monotonically increasing 3.”Dueling proposers problem”.

When two proposers want to propose simultaneously, they may try to block each other by issuing proposals with a number that is greater than the previous proposal. This situation could go on forever and violates termination. Possible solutions include leader election and random backoff.

Question:

1. What's the leader election algorithm in section 3?

2.The paper presents several optimizations, but it doesn't explain why and how these work will improve the performance of Paxos

3.As I read the paper, I felt that Paxos might be too difficult or costly to implement without any other optimizations

4.The assumption that the messages cannot be corrupted seems too strong

5.The paper seems somewhat incomplete. 1.it doesn’t address about the dueling proposers' problem described above as well as the solution. 2. How to choose the proposal number in order to make it globally unique and monotonically increasing? 3.What about membership management?

Related Links:

PreviousLogical Physical Clocks and Consistent Snapshots in Globally Distributed DatabasesNextZooKeeper: Wait-free coordination for Internet-scale systems

Last updated 5 years ago

Was this helpful?