Um Arcabouço de Simulação e Avaliação de Sistemas de Quóruns Bizantinos

• Wagner Saback Dantas UFSC
• Alysson Neves Bessani University of Lisboa
• Joni da Silva Fraga UFSC

DOI: https://doi.org/10.5753/wtf.2007.23249

Abstract

Byzantine Quorum Systems (BQS) have been described as a good choice to build Byzantine-tolerant reliable distributed storage, with many implementation approaches already proposed. Choosing the most suited one requires a careful evaluation aided by tools oriented to model and prototype Byzantine execution environments. To date, however, such facility does not exist. The paper presents BQSNeko, a framework useful for evaluating BQS algorithms. To show how this framework can be used, we discuss the results of an experiment built on BQSN EKO that compares two well-known Byzantine quorum protocols.

References

Barcellos, M., Woszezenki, C., and Munaretti, R. (2005). Framework de injeção de falhas simulada para avaliação de sistemas distribuídos. In Anais do 23o. Simpósio Brasileiro de Redes de Computadores - SBRC 2005, Fortaleza, CE, Brasil.

Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.

Goodson, G. R., Wylie, J. J., Ganger, G. R., and Reiter, M. K. (2004). Efficient byzantine-tolerant erasure-coded storage. In DSN ’04: Proceedings of the 2004 International Conference on Dependable Systems and Networks, page 135, Washington, DC, USA. IEEE Computer Society.

Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124–149.

Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565.

Lamport, L. (1986). On interprocess communication (part ii: algorithms). Distributed Computing, 1(1):203–213.

Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.

Liskov, B. and Rodrigues, R. (2006). Tolerating byzantine faulty clients in a quorum system. In ICDCS ’06: Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, page 34, Washington, DC, USA. IEEE Computer Society.

Malkhi, D. and Reiter, M. (1998a). Secure and scalable replication in Phalanx (extended abstract). In Proceedings of 17th Symposium on Reliable Distributed Systems, pages 51–60.

Malkhi, D. and Reiter, M. K. (1998b). Byzantine quorum systems. Distributed Computing, 11(4):203–213.

Martin, J.-P., Alvisi, L., and Dahlin, M. (2002a). Minimal Byzantine storage. In Distributed Computing, 16th international Conference, DISC 2002, volume 2508 of LNCS, pages 311–325.

Martin, J.-P., Alvisi, L., and Dahlin, M. (2002b). Small byzantine quorum systems. In DSN ’02: Proceedings of the 2002 International Conference on Dependable Systems and Networks, pages 374–388, Washington, DC, USA. IEEE Computer Society.

Obelheiro, R. R., Bessani, A. N., and Lung, L. C. (2005). Analisando a viabilidade da implementação prática de sistemas tolerantes a intrusões. In Anais do V Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais - SBSeg 2005.

Schneider, F. B. (1990). Implementing fault-tolerant service using the state machine aproach: A tutorial. ACM Computing Surveys, 22(4):299–319.

Urbán, P., Hayashibara, N., Schiper, A., and Katayama, T. (2004). Performance comparison of a rotating coordinator and a leader based consensus algorithm. In Proc. 23nd IEEE Int’l Symp. on Reliable Distributed Systems (SRDS), pages 4–17, Florianópolis, Brazil.

Urbán, P., Défago, X., and Schiper, A. (2000). Contention-aware metrics for distributed algorithms: Comparison of atomic broadcast algorithms. In Proceedings of the 9th IEEE Int’l Conference on Computer Communications and Networks (IC3N 2000).

Urbán, P., Défago, X., and Schiper, A. (2001). Neko: A single environment to simulate and prototype distributed algorithms. In Proceedings of the 15th Int’l Conf. on Information Networking (ICOIN-15), Beppu City, Japan.