Aspectos Práticos da Realização do Consenso FT-CUP em Redes Móveis Ad-Hoc
Resumo
O consenso é um problema fundamental no desenvolvimento de sistemas distribuídos confiáveis. As redes móveis ad-hoc (Manets) possuem alta dinamicidade, o que dificulta o conhecimento prévio dos participantes, fundamental para soluções clássicas do consenso. O problema do consenso tolerante a falhas com participantes desconhecidos passa a ser designado FT-CUP. Greve e Tixeuil propõem uma solução para o FT-CUP a partir da identificação de requisitos minimais de conectividade no grafo de conhecimento estabelecido pelos participantes e considerando-se os requisitos mínimos de sincronia para resolver o problema em presença de falhas. Este trabalho complementa Greve e Tixeuil e analisa os aspectos práticos da realização do FT-CUP em Manets. Ele propõe implementações para os algoritmos sugeridos e realiza diversas simulações em cenários variados. A partir dos resultados obtidos, chegou-se a um conjunto de parâmetros para os quais é possível a convergência do FT-CUP, definindo as características práticas de uma rede Manet onde o consenso pode ser resolvido.Referências
Basile, C., Killijian, M., and Powell, D. (2003). A survey of dependability issues in mobile wireless networks. Technical report, LAAS CNRS, Toulouse, France.
Cavin, D., Sasson, Y., and Schiper, A. (2004). Consensus with unknown participants or fundamental self-organization. In Third Int. Conf. on Ad hoc Net. and Wireless (ADHOC-NOW 2004), pages 135–148, Vancouver, Canada.
Cavin, D., Sasson, Y., and Schiper, A. (2005). Reaching agreement with unknown participants in mobile self-organized networks in spite of process crashes. Technical report, Ecole Polytechnique Federale de Lausanne.
Chandra, T. D., Hadzilacos, V., and Toueg, S. (1996). The weakest failure detector for solving consensus. J. ACM, 43(4):685–722.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225–267.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382.
Greve, F. and Tixeuil, S. (2007). Knowledge conectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. DSN 2007 Int. Conf. Dependable Systems and Networks, to be published.
Kurkowski, S., Camp, T., and Colagrosso, M. (2005). Manet simulation studies: the incredibles. SIGMOBILE Mob. Comput. Commun. Rev., 9(4):50–61.
Larrea, M., Fernandez, A., and Arevalo, S. (2004). On the implementation of unreliable failure detectors in partially synchronous systems. IEEE Transactions on Computers, 53(7):815–828.
Mostéfaoui, A. and Raynal, M. (1999). Solving consensus using Chandra-Toueg’s unreliable failure detectors: A general quorum-based approach. In 13th Int. Symp. on Distributed Computing (DISC’99), volume 1693 of LNCS, pages 49–63.
Oliveira, T., Costa, V., Greve, F., and Schnitman, L. (2006). Evaluating the impact of faults on broadcasting protocols for manets. In WTF 2006 VII Workshop de Testes e Tolerância a Falhas, pages 49–60.
Varga, A. (2001). The OMNeT++ discrete event simulation system. In European Simulation Multiconference (ESM’2001), Prague, Czech Republic.
Cavin, D., Sasson, Y., and Schiper, A. (2004). Consensus with unknown participants or fundamental self-organization. In Third Int. Conf. on Ad hoc Net. and Wireless (ADHOC-NOW 2004), pages 135–148, Vancouver, Canada.
Cavin, D., Sasson, Y., and Schiper, A. (2005). Reaching agreement with unknown participants in mobile self-organized networks in spite of process crashes. Technical report, Ecole Polytechnique Federale de Lausanne.
Chandra, T. D., Hadzilacos, V., and Toueg, S. (1996). The weakest failure detector for solving consensus. J. ACM, 43(4):685–722.
Chandra, T. D. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225–267.
Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382.
Greve, F. and Tixeuil, S. (2007). Knowledge conectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. DSN 2007 Int. Conf. Dependable Systems and Networks, to be published.
Kurkowski, S., Camp, T., and Colagrosso, M. (2005). Manet simulation studies: the incredibles. SIGMOBILE Mob. Comput. Commun. Rev., 9(4):50–61.
Larrea, M., Fernandez, A., and Arevalo, S. (2004). On the implementation of unreliable failure detectors in partially synchronous systems. IEEE Transactions on Computers, 53(7):815–828.
Mostéfaoui, A. and Raynal, M. (1999). Solving consensus using Chandra-Toueg’s unreliable failure detectors: A general quorum-based approach. In 13th Int. Symp. on Distributed Computing (DISC’99), volume 1693 of LNCS, pages 49–63.
Oliveira, T., Costa, V., Greve, F., and Schnitman, L. (2006). Evaluating the impact of faults on broadcasting protocols for manets. In WTF 2006 VII Workshop de Testes e Tolerância a Falhas, pages 49–60.
Varga, A. (2001). The OMNeT++ discrete event simulation system. In European Simulation Multiconference (ESM’2001), Prague, Czech Republic.
Publicado
29/05/2007
Como Citar
COSTA, Victor Franco; GREVE, Fabíola Gonçalves Pereira.
Aspectos Práticos da Realização do Consenso FT-CUP em Redes Móveis Ad-Hoc. 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. 189-202.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2007.23248.
