Um Arcabouço de Simulação e Avaliação de Sistemas de Quóruns Bizantinos
Resumo
Sistemas de Quóruns Bizantinos (BQS) têm sido apresentados como uma boa estratégia de construção de armazenamento distribuído tolerante a faltas bizantinas, havendo muitas abordagens para sua implementação. Escolher a abordagem mais adequada requer uma avaliação minuciosa com a ajuda de ferramentas orientadas à modelagem e prototipação de ambientes bizantinos de execução. Até então, porém, não se conhecia uma ferramenta que facilitasse tal análise. O artigo apresenta o arcabouço de avaliação de algoritmos de BQS BQSN EKO . Para mostrar a sua utilidade, serão discutidos os resultados de um experimento construído no BQSN EKO com dois algoritmos de BQS conhecidos.Referências
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.
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.
Publicado
29/05/2007
Como Citar
DANTAS, Wagner Saback; BESSANI, Alysson Neves; FRAGA, Joni da Silva.
Um Arcabouço de Simulação e Avaliação de Sistemas de Quóruns Bizantinos. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 8. , 2007, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 203-216.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2007.23249.
