Does Paxos consensus algorithm scale linearly?
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.


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.