PAXOS – I’m coming for you!

March 15, 2021 | minutes read

I’m now half way through Distributed Computing course at Georgia Tech and us students are now tackling the penultimate project: building a replicated state machine using PAXOS. This project will be challenging (probably going to require 40+ hours) and it’ll put my theoretical knowledge to the test and reflect back, in a couple weeks, how much I learned.

Presently, here’s my little understanding of the consensus algorithm:

Current PAXOS understanding

  • Servers play different roles – Proposer, Acceptor, Learner
  • Proposers send proposals that monotonically increase
  • Proposals are accepted if and only if a majority of the quorum accept them
  • The 2PC (2 phased commit) protocol essentially tells us whether or not a particular transaction is committed or aborted
  • Guaranteeing linearzability means that, from the clients perspective, real time (i.e. wall clock) should be respected and the client should view the system as if there is a single replica

Future PAXOS understanding

  • How exactly PAXOS guarantees consensus via its 2 phased commit protocol
  • How does a server determine its role (or does it play multiple roles)
  • How to handle the edge cases (say two proposals arrive at the same time)
  • What role does a client play? Does it serve as a proposer?
  • How does leader election work in PAXOS?
  • Should I just try and mimic the Python based code described in Paxos made moderately difficult
  • How will replication work as the number of nodes in the system scales (say from 3 to 5 to 10)
  • How to detect (and perhaps avoid) split brain (i.e. multiple leaders)


  1. Majority quorum can be defined as floor(n/2) + 1
  2. Python implementation described

I’m Matt Chung. I’m a software engineer, seasoned technology leader, and father currently based in Seattle and London. I love to share what I know. I write about topic developing scalable & fail-safe software running in the AWS cloud, digital organization as a mechanism for unlocking your creativity, and maximizing our full potentials with personal development habits.

View all articles