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.