Analisando o Custo do Armazenamento Tolerante a Faltas Bizantinas: PAXOS x Sistemas de Quóruns
Resumo
A manutenção da disponibilidade e da integridade das informações é um requisito fundamental em sistemas de armazenamento de dados tolerantes a faltas. Uma abordagem comumente utilizada para concretização destes sistemas é a replicação tolerante a faltas Bizantinas. O presente trabalho avalia duas técnicas que podem ser utilizadas para a implementação de sistemas de armazenamento tolerantes a faltas Bizantinas: replicação máquina de estados, baseada no algoritmo PAXOS Bizantino, e sistemas de quóruns Bizantinos. Nossa abordagem compara teórica e experimentalmente duas implementações de um serviço de armazenamento, cada uma baseada em uma destas técnicas. Os resultados demonstram claramente as vantagens e desvantagens destas abordagens quando consideramos uma rede local e um número mínimo de réplicas.
Referências
Abd-El-Malek, M., Ganger, G., Goodson, G., Reiter, M., and Wylie, J. (2005). Fault-scalable Byzantine fault-tolerant services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles - SOSP’05, pages 59–74.
Bazzi, R. A. and Ding, Y. (2004). Non-skipping timestamps for Byzantine data storage systems. In Proc. of 18th Int. Symposium on Distributed Computing, DISC 2004, volume 3274 of LNCS, pages 405–419.
Cachin, C. and Tessaro, S. (2006). Optimal resilience for erasure-coded Byzantine distributed storage. In Proceedings of the International Conference on Dependable Systems and Networks - DSN 2006.
Castro, M. and Liskov, B. (2002). Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Ekwall, R. and Schiper, A. (2005). Replication: Understanding the advantage of atomic broadcast over quorum systems. Journal of Universal Computer Science, 11(5):703–711.
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 Proceedings of International Conference on Dependable Systems and Networks - DSN 2004.
Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124–149.
Lamport, L. (1986). On interprocess communication (part II). 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. S. M. (2006). Tolerating byzantine faulty clients in a quorum system. In The 26th IEEE International Conference on Distributed Computing Systems - ICDCS 2006.
Malkhi, D. and Reiter, M. (1998). Byzantine quorum systems. Distributed Computing, 11(4):203–213.
Martin, J.-P. and Alvisi, L. (2005). Fast Byzantine consensus. In Proceedings of the Dependable Systems and Networks - DSN-2005.
Martin, J.-P., Alvisi, L., and Dahlin, M. (2002). Minimal Byzantine storage. In Proceedings of the 16th International Symposium on Distributed Computing - DISC 2002, volume 2508 of LNCS, pages 311–325.
Moniz, H., Neves, N. F., Correia, M., and Verı́ssimo, P. (2006). Randomized intrusion-tolerant asynchronous services. In Proceedings of the International Conference on Dependable Systems and Networks - DSN 2006.
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.
Pedone, F. and Schiper, A. (1998). Optimistic atomic broadcast. In Proceedings of the 12th International Symposium on Distributed Computing - DISC’98.
Schneider, F. B. (1990). Implementing fault-tolerant service using the state machine aproach: A tutorial. ACM Computing Surveys, 22(4):299–319.
Toueg, S. (1984). Randomized Byzantine agreements. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing, pages 163–178.
Urbán, P., Défago, X., and Schiper, A. (2001). Chasing the FLP impossibility in a LAN or how robust can a fault tolerant server be? In Proceedings of the 20th IEEE Symposium on Reliable Distributed Systems - SRDS’01, pages 190–193.
Urbán, P., Défago, X., and Schiper, A. (2002). Neko: A single environment to simulate and prototype distributed algorithms. Journal of Information Science and Engineering, 18(6):981–997.
Zhou, L., Schneider, F., and Van Rennesse, R. (2002). COCA: A secure distributed online certification authority. ACM Transactions on Computer Systems, 20(4):329–368.
Zielinski, P. (2004). Paxos at War. Technical Report UCAM-CL-TR-593, University of Cambridge Computer Laboratory, Cambridge, UK.
Bazzi, R. A. and Ding, Y. (2004). Non-skipping timestamps for Byzantine data storage systems. In Proc. of 18th Int. Symposium on Distributed Computing, DISC 2004, volume 3274 of LNCS, pages 405–419.
Cachin, C. and Tessaro, S. (2006). Optimal resilience for erasure-coded Byzantine distributed storage. In Proceedings of the International Conference on Dependable Systems and Networks - DSN 2006.
Castro, M. and Liskov, B. (2002). Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398–461.
Ekwall, R. and Schiper, A. (2005). Replication: Understanding the advantage of atomic broadcast over quorum systems. Journal of Universal Computer Science, 11(5):703–711.
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 Proceedings of International Conference on Dependable Systems and Networks - DSN 2004.
Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124–149.
Lamport, L. (1986). On interprocess communication (part II). 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. S. M. (2006). Tolerating byzantine faulty clients in a quorum system. In The 26th IEEE International Conference on Distributed Computing Systems - ICDCS 2006.
Malkhi, D. and Reiter, M. (1998). Byzantine quorum systems. Distributed Computing, 11(4):203–213.
Martin, J.-P. and Alvisi, L. (2005). Fast Byzantine consensus. In Proceedings of the Dependable Systems and Networks - DSN-2005.
Martin, J.-P., Alvisi, L., and Dahlin, M. (2002). Minimal Byzantine storage. In Proceedings of the 16th International Symposium on Distributed Computing - DISC 2002, volume 2508 of LNCS, pages 311–325.
Moniz, H., Neves, N. F., Correia, M., and Verı́ssimo, P. (2006). Randomized intrusion-tolerant asynchronous services. In Proceedings of the International Conference on Dependable Systems and Networks - DSN 2006.
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.
Pedone, F. and Schiper, A. (1998). Optimistic atomic broadcast. In Proceedings of the 12th International Symposium on Distributed Computing - DISC’98.
Schneider, F. B. (1990). Implementing fault-tolerant service using the state machine aproach: A tutorial. ACM Computing Surveys, 22(4):299–319.
Toueg, S. (1984). Randomized Byzantine agreements. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing, pages 163–178.
Urbán, P., Défago, X., and Schiper, A. (2001). Chasing the FLP impossibility in a LAN or how robust can a fault tolerant server be? In Proceedings of the 20th IEEE Symposium on Reliable Distributed Systems - SRDS’01, pages 190–193.
Urbán, P., Défago, X., and Schiper, A. (2002). Neko: A single environment to simulate and prototype distributed algorithms. Journal of Information Science and Engineering, 18(6):981–997.
Zhou, L., Schneider, F., and Van Rennesse, R. (2002). COCA: A secure distributed online certification authority. ACM Transactions on Computer Systems, 20(4):329–368.
Zielinski, P. (2004). Paxos at War. Technical Report UCAM-CL-TR-593, University of Cambridge Computer Laboratory, Cambridge, UK.
Publicado
29/05/2006
Como Citar
BESSANI, Alysson Neves; DANTAS, Wagner Saback; ALCHIERI, Eduardo Adílio Pelinson; FRAGA, Joni da Silva.
Analisando o Custo do Armazenamento Tolerante a Faltas Bizantinas: PAXOS x Sistemas de Quóruns. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 7. , 2006, Curitiba/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2006
.
p. 49-60.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2006.23351.
