Coordenação Desacoplada Tolerante a Faltas Bizantinas
Resumo
Os sistemas distribuídos atuais requerem mecanismos de comunicação que atendam requisitos como anonimato e desconexão temporária. Neste contexto, a comunicação generativa vêm se afirmando como um dos modelos de coordenação capazes de atender esses requisitos uma vez que é desacoplada no tempo e no espaço. Este trabalho apresenta a primeira proposta da literatura a considerar a construção de uma infra-estrutura de coordenação generativa tolerante a faltas bizantinos. Esta construção se dá através da aplicação de replicação por sistemas de quóruns bizantinos.Referências
Bakken, D. E. and Schlichting, R. D. (1995). Supporting fault-tolerant parallel programing in linda. IEEE Transactions on Parallel and Distributed Systems, 6(3):287–302.
Bessani, A. N., da Silva Fraga, J., and Lung, L. C. (2005a). Coordenação desacoplada tolerante a faltas bizantinas. http://www.das.ufsc.br/∼neves/reports/2005-2.pdf.
Bessani, A. N., da Silva Fraga, J., and Lung, L. C. (2005b). O confeiteiro bizantino: Exclusão mútua em sistemas abertos sujeitos a faltas bizantinas. In Anais do 23º. Simpósio Brasileiro de Redes de Computadores - SBRC 2005, Fortaleza, CE, Brasil.
Busi, N., Gorrieri, R., Lucchi, R., and Zavattaro, G. (2003). Secspaces: a data-driven coordination model for environments open to untrusted agents. In Brogi, A. and Jacquet, J.-M., editors, Electronic Notes in Theoretical Computer Science, volume 68. Elsevier.
Cabri, G., Leonardi, L., and Zambonelli, F. (2000). Mobile agents coordination models for internet applications. IEEE Computer, 33(2):82–89.
Carriero, N. and Gelernter, D. (1989). Linda in context. Communications of the ACM, 32(4):444–458.
Castro, M., Rodrigues, R., and Liskov, B. (2003). Base: Using abstraction to improve fault tolerance. ACM Transactions Computer Systems, 21(3):236–269. A preliminar version appeared 18th Symposium on Operating Systems Principles, 2001.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2).
Chiba, S., Kato, K., and Masuda, T. (1992). Exploiting a weak consistency to implement distributed tuple space. In Proceedings of the 12th International Conference on Distributed Computing Systems - ICDCS’92., pages 416–423, Yokohama, Japan. IEEE Computer Society Press.
De Nicola, R., Ferrari, G. L., and Pugliese, R. (1998). Klaim: A kernel language for agents interaction and mobility. IEEE Transactions on Software Engineering, 24(5):315–330.
Doudou, A., Garbinato, B., Guerraoui, R., and Schiper, A. (1999). Muteness failure detectors: Specification and implementation. In Proceedings of the 3rd European Dependable Computing Conference. Springer-Verlag.
Eugster, P. T., Felber, P. A., Guerraoui, R., and Kermarrec, A.-M. (2003). The many faces of publish/subscribe. ACM Computing Surveys, 35(2):114–131.
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.
Fraga, J. and Powell, D. (1985). A fault- and intrusion-tolerant file system. In Proceedings of the 3rd International Conference on Computer Security, pages 203–218.
Gelernter, D. (1985). Generative communication in linda. ACM Transactions on Programing Languages and Systems, 7(1):80–112.
Gelernter, D. and Carriero, N. (1992). Coordination languages and their significance. Communications of ACM, 35(2):96–107.
Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124–149. Dijkstra Prize 2003 winner.
Lamport, L., Shostak, R., and Pease, M. (1982). The byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Lehman, T. J., Cozzi, A., Xiong, Y., Gottschalk, J., Vasudevan, V., Landis, S., Davis, P., Khavar, B., and Bowman, P. (2001). Hitting the distributed computing sweet spot with TSpaces. Computer Networks, 35(4):457–472.
Lynch, N. A. (1996). Distributed Algorithms. Morgan Kauffman, San Francisco - California.
Malkhi, D. and Reiter, M. (1998). Byzantine quorum systems. Distributed Computing, 11(4):203–213.
Martin, J.-P., Alvisi, L., and Dahlin, M. (2001). Small byzantine quorum systems. In Dependable Systems and Networks, DSN 01. IEEE Computer Society.
Martin, J.-P., Alvisi, L., and Dahlin, M. (2002). Minimal Byzantine storage. In Distributed Computing, 16th international Conference, DISC 2002, volume 2508 of LNCS, pages 311–325. Springer-Verlag.
Minsky, N. H., Minsky, Y. M., and Ungureanu, V. (2000). Making tuple spaces safe for heterogeneous distributed systems. In Proceedings of the 2000 ACM symposium on Applied computing, pages 218–226. ACM Press.
Papadopolous, G. and Arbab, F. (1998). Coordination models and languages. In The Engineering of Large Systems, volume 46 of Advances in Computers. Academic Press.
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.
Sun Microsystems (2003). Javaspaces service specification. Disponível em http://www.jini.org/nonav/standards/davis/doc/specs/html/js-spec.html.
Veríssimo, P., Neves, N. F., and Correia, M. P. (2003). Intrusion-tolerant architectures: Concepts and design. Technical Report DI-FCUL TR-03-5, Universidade de Lisboa, Lisboa, Portugal.
Vitek, J., Bryce, C., and Oriol, M. (2003). Coordination processes with secure spaces. Science of Computer Programming, (46):163–193.
Xu, A. and Liskov, B. (1989). A design for a fault-tolerant, distributed implementation of linda. In Proceedings of the 19th Symposium on Fault-Tolerant Computing - FTCS’89., pages 199–206. IEEE Computer Society Press.
Bessani, A. N., da Silva Fraga, J., and Lung, L. C. (2005a). Coordenação desacoplada tolerante a faltas bizantinas. http://www.das.ufsc.br/∼neves/reports/2005-2.pdf.
Bessani, A. N., da Silva Fraga, J., and Lung, L. C. (2005b). O confeiteiro bizantino: Exclusão mútua em sistemas abertos sujeitos a faltas bizantinas. In Anais do 23º. Simpósio Brasileiro de Redes de Computadores - SBRC 2005, Fortaleza, CE, Brasil.
Busi, N., Gorrieri, R., Lucchi, R., and Zavattaro, G. (2003). Secspaces: a data-driven coordination model for environments open to untrusted agents. In Brogi, A. and Jacquet, J.-M., editors, Electronic Notes in Theoretical Computer Science, volume 68. Elsevier.
Cabri, G., Leonardi, L., and Zambonelli, F. (2000). Mobile agents coordination models for internet applications. IEEE Computer, 33(2):82–89.
Carriero, N. and Gelernter, D. (1989). Linda in context. Communications of the ACM, 32(4):444–458.
Castro, M., Rodrigues, R., and Liskov, B. (2003). Base: Using abstraction to improve fault tolerance. ACM Transactions Computer Systems, 21(3):236–269. A preliminar version appeared 18th Symposium on Operating Systems Principles, 2001.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2).
Chiba, S., Kato, K., and Masuda, T. (1992). Exploiting a weak consistency to implement distributed tuple space. In Proceedings of the 12th International Conference on Distributed Computing Systems - ICDCS’92., pages 416–423, Yokohama, Japan. IEEE Computer Society Press.
De Nicola, R., Ferrari, G. L., and Pugliese, R. (1998). Klaim: A kernel language for agents interaction and mobility. IEEE Transactions on Software Engineering, 24(5):315–330.
Doudou, A., Garbinato, B., Guerraoui, R., and Schiper, A. (1999). Muteness failure detectors: Specification and implementation. In Proceedings of the 3rd European Dependable Computing Conference. Springer-Verlag.
Eugster, P. T., Felber, P. A., Guerraoui, R., and Kermarrec, A.-M. (2003). The many faces of publish/subscribe. ACM Computing Surveys, 35(2):114–131.
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.
Fraga, J. and Powell, D. (1985). A fault- and intrusion-tolerant file system. In Proceedings of the 3rd International Conference on Computer Security, pages 203–218.
Gelernter, D. (1985). Generative communication in linda. ACM Transactions on Programing Languages and Systems, 7(1):80–112.
Gelernter, D. and Carriero, N. (1992). Coordination languages and their significance. Communications of ACM, 35(2):96–107.
Herlihy, M. (1991). Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124–149. Dijkstra Prize 2003 winner.
Lamport, L., Shostak, R., and Pease, M. (1982). The byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.
Lehman, T. J., Cozzi, A., Xiong, Y., Gottschalk, J., Vasudevan, V., Landis, S., Davis, P., Khavar, B., and Bowman, P. (2001). Hitting the distributed computing sweet spot with TSpaces. Computer Networks, 35(4):457–472.
Lynch, N. A. (1996). Distributed Algorithms. Morgan Kauffman, San Francisco - California.
Malkhi, D. and Reiter, M. (1998). Byzantine quorum systems. Distributed Computing, 11(4):203–213.
Martin, J.-P., Alvisi, L., and Dahlin, M. (2001). Small byzantine quorum systems. In Dependable Systems and Networks, DSN 01. IEEE Computer Society.
Martin, J.-P., Alvisi, L., and Dahlin, M. (2002). Minimal Byzantine storage. In Distributed Computing, 16th international Conference, DISC 2002, volume 2508 of LNCS, pages 311–325. Springer-Verlag.
Minsky, N. H., Minsky, Y. M., and Ungureanu, V. (2000). Making tuple spaces safe for heterogeneous distributed systems. In Proceedings of the 2000 ACM symposium on Applied computing, pages 218–226. ACM Press.
Papadopolous, G. and Arbab, F. (1998). Coordination models and languages. In The Engineering of Large Systems, volume 46 of Advances in Computers. Academic Press.
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.
Sun Microsystems (2003). Javaspaces service specification. Disponível em http://www.jini.org/nonav/standards/davis/doc/specs/html/js-spec.html.
Veríssimo, P., Neves, N. F., and Correia, M. P. (2003). Intrusion-tolerant architectures: Concepts and design. Technical Report DI-FCUL TR-03-5, Universidade de Lisboa, Lisboa, Portugal.
Vitek, J., Bryce, C., and Oriol, M. (2003). Coordination processes with secure spaces. Science of Computer Programming, (46):163–193.
Xu, A. and Liskov, B. (1989). A design for a fault-tolerant, distributed implementation of linda. In Proceedings of the 19th Symposium on Fault-Tolerant Computing - FTCS’89., pages 199–206. IEEE Computer Society Press.
Publicado
09/05/2005
Como Citar
BESSANI, Alysson Neves; FRAGA, Joni da Silva; LUNG, Lau Cheuk.
Coordenação Desacoplada Tolerante a Faltas Bizantinas. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 6. , 2005, Fortaleza/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2005
.
p. 1-12.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2005.23363.
