Algoritmo de Consenso Genérico em Memória Compartilhada

• Cátia Khouri UESB
• Fabíola Greve UESB

DOI: https://doi.org/10.5753/wtf.2013.23015

Abstract

Consensus is a fundamental problem for the development of reliable distributed systems. However, in asynchronous environments prone to failures, it is necessary to extend the system with some mechanism that provides the minimum synchrony necessary to circumvent the impossibility of consensus. In this paper, we present a generic consensus algorithm for asynchronous system with shared memory that can be instantiated with a failure detector ◊S or Ω. The algorithm is optimal regarding the number of registers it uses and it tolerates (n − 1) failures. This solution for shared memory favors the use of consensus in modern applications developed, for example, on multicore architectures and Storage Area Networks (SAN).

References

Aguilera, M. K., Englert, B., and Gafni, E. (2003). On using network attached disks as shared memory. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, PODC ’03, pages 315–324, New York, NY, USA. ACM.

Chandra, T. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.

Chandra, T. D., Hadzilacos, V., and Toueg, S. (1996). The weakest failure detector for solving consensus. Journal of the ACM, 43(4):685–722.

Delporte-Gallet, C. and Fauconnier, H. (2009). Two consensus algorithms with atomic registers and failure detector omega. In Proceedings of the 10th International Conference on Distributed Computing and Networking, ICDCN ’09, pages 251–262, Berlin, Heidelberg. Springer-Verlag.

Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Hadzilacos, V., Kouznetsov, P., and Toueg, S. (2004). The weakest failure detectors to solve certain fundamental problems in distributed computing. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, PODC ’04, pages 338–346, New York, NY, USA. ACM.

Fischer, M. J., Lynch, N. A., and Paterson, M. D. (1985). Impossibility of distributed consensus with one faulty process. Journal of ACM, 32(2):374–382.

Guerraoui, R. and Raynal, M. (2003). The information structure of indulgent consensus. IEEE Transactions on Computers, 53:2004.

Guerraoui, R. and Raynal, M. (2007). The alpha of indulgent consensus. Comput. J., 50(1):53–67.

Khouri, C., Greve, F., and Tixeuil, S. (2012). Consenso com participantes desconhecidos em memoria compartilhada. 30o SBRC, Porto Alegre, RS, Brasil. SBC.

Lamport, L. (1986). On interprocess communication. Distributed Computing, 1(2):77–101.

Lo, W.-K. and Hadzilacos, V. (1994). Using failure detectors to solve consensus in asynchronous shared-memory systems (extended abstract). In Proceedings of the 8th International Workshop on Distributed Algorithms, WDAG ’94, pages 280–295, London, UK. Springer-Verlag.

Loui, M. C. and Abu-Amara, H. H. (1987). Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163–183.