Resolução do Consenso em Redes Móveis Ad-Hoc a Partir de um Conjunto Dominante Conexo
Resumo
O presente trabalho apresenta uma nova abordagem para a solução do consenso em redes móveis auto-organizáveis, baseada na construção de um conjunto dominante conexo de nós sobre a topologia da rede. Emprega-se abstrações para a detecção e o monitoramento de participantes a fim de manter as propriedades deste conjunto dinâmico na presença de falhas e mobilidade de processos. O resultado é uma estruturação lógica da rede baseada em seu estado real, que permite a realização de cálculos distribuídos consistentes, como a solução do consenso tolerante a falhas entre participantes desconhecidos.Referências
Cavin, D., Sasson, Y., and Schiper, A. (2004). Consensus with Unknown Participants or Fundamental Self-Organization. Lecture Notes in Computer Science, pages 135–148.
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, Research Report IC/2005/026, EPFL, 2005.
Chandra, T. and Toueg, S. (1996). Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the Association for Computing Machinery, 43(2):225–267.
Dai, F. and Wu, J. (2003). Distributed Dominant Pruning in Ad Hoc Networks. In IEEE International Conference on Communications, 2003. ICC’03, volume 1, pages 353–357.
Dai, F. and Wu, J. (2005). On constructing k-connected k-dominating set in wireless networks. In 19th IEEE International Parallel and Distributed Processing Symposium, 2005. Proceedings, page 81a.
Daniel Cason, F. G. P. G. (2009). Desenvolvimento de aplicações confiáveis em MANET a partir de um conjunto dominante conexo. Trabalho de conclusão de curso, Universidade Federal da Bahia. Disponível em [link].
Das, B. and Bharghavan, V. (1997). Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets. In 1997 IEEE International Conference on Communications, 1997. ICC 97 Montreal,’Towards the Knowledge Millennium’, volume 1, pages 376–380.
Fischer, M., Lynch, N., and Paterson, M. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM (JACM), 32(2):374–382.
Greve, F. (2005). Protocolos fundamentais para o desenvolvimento de aplicações robustas. In Minicursos SBRC 2005: Brazilian Symposium on Computer Networks, pages 330–398, Fortaleza, CE, Brazil.
Greve, F. and Tixeuil, S. (2007). Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. In Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 82–91. IEEE Computer Society Washington, DC, USA.
Guha, S. (1996). Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387.
Hutle, M. and Widder, J. (2004). Time free self-stabilizing local failure detection. Research Report 33, TU Wien, Technische Universität Wien.
Karp, R. (1972). Reducibility among Combinatorial Problems. Complexity of computer computations: proceedings, page 85.
Si, W. and Li, C. (2004). Rmac: A reliable multicast mac protocol for wireless ad hoc networks. In ICPP ’04: Proceedings of the 2004 International Conference on Parallel Processing, pages 494–501, Washington, DC, USA. IEEE Computer Society.
Sridhar, N. (2006). Decentralized local failure detection in dynamic distributed systems. In The 25th IEEE Symposium on Reliable Distributed Systems, pages 143–154.
Wu, J. (2002). Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE Transactions on Parallel and Distributed Systems, 13(9):866–881.
Wu, J. and Dai, F. (2004). A generic distributed broadcast scheme in ad hoc wireless networks. IEEE Transactions on Computers, 53(10):1343–1354.
Wu, J. and Li, H. (1999). On calculating connected dominating set for efficient routing in ad hoc wireless networks. In DIALM ’99: Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, pages 7–14, New York, NY, USA. ACM.
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, Research Report IC/2005/026, EPFL, 2005.
Chandra, T. and Toueg, S. (1996). Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the Association for Computing Machinery, 43(2):225–267.
Dai, F. and Wu, J. (2003). Distributed Dominant Pruning in Ad Hoc Networks. In IEEE International Conference on Communications, 2003. ICC’03, volume 1, pages 353–357.
Dai, F. and Wu, J. (2005). On constructing k-connected k-dominating set in wireless networks. In 19th IEEE International Parallel and Distributed Processing Symposium, 2005. Proceedings, page 81a.
Daniel Cason, F. G. P. G. (2009). Desenvolvimento de aplicações confiáveis em MANET a partir de um conjunto dominante conexo. Trabalho de conclusão de curso, Universidade Federal da Bahia. Disponível em [link].
Das, B. and Bharghavan, V. (1997). Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets. In 1997 IEEE International Conference on Communications, 1997. ICC 97 Montreal,’Towards the Knowledge Millennium’, volume 1, pages 376–380.
Fischer, M., Lynch, N., and Paterson, M. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM (JACM), 32(2):374–382.
Greve, F. (2005). Protocolos fundamentais para o desenvolvimento de aplicações robustas. In Minicursos SBRC 2005: Brazilian Symposium on Computer Networks, pages 330–398, Fortaleza, CE, Brazil.
Greve, F. and Tixeuil, S. (2007). Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. In Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 82–91. IEEE Computer Society Washington, DC, USA.
Guha, S. (1996). Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387.
Hutle, M. and Widder, J. (2004). Time free self-stabilizing local failure detection. Research Report 33, TU Wien, Technische Universität Wien.
Karp, R. (1972). Reducibility among Combinatorial Problems. Complexity of computer computations: proceedings, page 85.
Si, W. and Li, C. (2004). Rmac: A reliable multicast mac protocol for wireless ad hoc networks. In ICPP ’04: Proceedings of the 2004 International Conference on Parallel Processing, pages 494–501, Washington, DC, USA. IEEE Computer Society.
Sridhar, N. (2006). Decentralized local failure detection in dynamic distributed systems. In The 25th IEEE Symposium on Reliable Distributed Systems, pages 143–154.
Wu, J. (2002). Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE Transactions on Parallel and Distributed Systems, 13(9):866–881.
Wu, J. and Dai, F. (2004). A generic distributed broadcast scheme in ad hoc wireless networks. IEEE Transactions on Computers, 53(10):1343–1354.
Wu, J. and Li, H. (1999). On calculating connected dominating set for efficient routing in ad hoc wireless networks. In DIALM ’99: Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, pages 7–14, New York, NY, USA. ACM.
Publicado
31/08/2009
Como Citar
CASON, Daniel; GREVE, Fabíola Gonçalves Pereira.
Resolução do Consenso em Redes Móveis Ad-Hoc a Partir de um Conjunto Dominante Conexo. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 10. , 2009, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 20-33.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2009.23131.
