I'm trying to build a P2P web application using Paxos to obtain a consensus value.

How well does Paxos scale? linearly? or what kind of distribution can you expect? E.g. in using 10 to 10,000 users in the network.

If not, are there consensus algorithms that scale well?

  • 3
    $\begingroup$ If your plan is to treat each peer as part of the Paxos cluster, then this is going to perform extraordinarily poorly. This is not how you use Paxos (or any other consensus algorithm). Usually, you'll use a small number of nodes (3-8 typically) to elect a leader for a time period who, during that time period, can unilaterally make decisions. If that leader fails, Paxos is used to elect a new leader for a future, non-overlapping time period. (This is assuming you even need consensus.) $\endgroup$ Commented Aug 24, 2017 at 3:47

1 Answer 1


Apologies if this answer does not belong to this site

According to this paper released in 2013 which compares the performance over scale of Paxos and an optimized version of it Fast Paxos

Paxos and Fast Paxos are optimal consensus algorithms that are simple and elegant, while suitable for efficient implementation

Reading further section 3.4. Scale Up , you can find two graph plots. enter image description here

The left plot shows the number of requests served on y-axis and the number of replicas on x-axis. The right plot displays the average response time on y-axis and the number of replicas on x-axis.

I think it gives an idea about what one should expect.They are optimal choices according to the paper and I don't know of any other

As far as it goes for the running time , I think I read somewhere that it's linear.

  • 1
    $\begingroup$ In regards to my comment on the question, note the vertical axis on the second graph. At 13 replicas, the latency is already 1 second. If this aspect scaled linearly, you would be looking at latencies of like 15 minutes for 10,000 replicas. $\endgroup$ Commented Aug 24, 2017 at 3:50
  • $\begingroup$ @DerekElkins agreed $\endgroup$ Commented Aug 24, 2017 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.