Experimental Comparison of Local and Shared Coin Randomized Consensus Protocols

Henrique Moniz, Nuno Ferreira Neves, Miguel Correia, Paulo VerĂ­ssimo

Proceedings of the 25th IEEE Symposium on Reliable Distributed Systems (SRDS), Leeds, UK, October 2006.


Abstract

The paper presents a comparative performance study of the two main classes of randomized binary consensus protocols: a local coin protocol, with an expected high communication complexity and cheap symmetric cryptography, and a shared coin protocol, with an expected low communication complexity and expensive asymmetric cryptography. The experimental evaluation was conducted on a LAN environment, by varying several system parameters, such as the fault types and number of processes. The analysis shows that there is a significant gap between the theoretical and the practical performance results of these protocols, and provides an important insight into what actually happens during their execution.
 


BibTeX

@InProceedings{moniz06comparison,
    author = {Henrique Moniz and Nuno Ferreira Neves and Miguel Correia and Paulo Ver\'{\i}ssimo},
    title = {Experimental Comparison of Local and Shared Coin Randomized Consensus Protocols},
    booktitle = {Proceedings of the 25th IEEE Symposium on Reliable Distributed Systems (SRDS), Leeds, UK, October 2006},
    year = {2006},
    month = {oct}
}


Extended Version

Download the pdf.