Advertisement

Revisiting Failure Detection and Consensus in Omission Failure Environments

  • Carole Delporte-Gallet
  • Hugues Fauconnier
  • Felix C. Freiling
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)

Abstract

It has recently been shown that fair exchange, a security problem in distributed systems, can be reduced to a fault tolerance problem, namely a special form of distributed consensus. The reduction uses the concept of security modules which reduce the type and nature of adversarial behavior to two standard fault-assumptions: message omission and process crash. In this paper, we investigate the feasibility of solving consensus in asynchronous systems in which crash and message omission faults may occur. Due to the impossibility result of consensus in such systems, following the lines of unreliable failure detectors of Chandra and Toueg, we add to the system a distributed device that gives information about the failure of other processes. Then we give an algorithm using this device to solve the consensus problem. Finally, we show how to implement such a device in an asynchronous system using some weak timing assumptions.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Aguilera, M., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Stable leader election (extended abstract). In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 108–122. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  2. 2.
    Aguilera, M., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Communication-efficient leader election and consensus with limited link synchrony. In: 23rd ACM Symposium on Principles of Distributed Computing (PODC), St. Johns, Newfoundland, Canada, pp. 328–337 (2004)Google Scholar
  3. 3.
    Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: On implementing Omega with weak reliability and synchrony assumptions. In: 22nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 306–314 (2003)Google Scholar
  4. 4.
    Avoine, G., Gärtner, F.C., Guerraoui, R., Vukolic, M.: Gracefully degrading fair exchange with security modules. In: Dal Cin, M., Kaâniche, M., Pataricza, A. (eds.) EDCC 2005. LNCS, vol. 3463, pp. 55–71. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  5. 5.
    Chandra, T.D., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)zbMATHMathSciNetGoogle Scholar
  6. 6.
    Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)zbMATHMathSciNetGoogle Scholar
  7. 7.
    Delporte-Gallet, C., Fauconnier, H., Freiling, F.C.: Revisiting failure detection and consensus in omission failure environments. Technical Report AIB-2005-13, RWTH Aachen (June 2005)Google Scholar
  8. 8.
    Dolev, D., Friedman, R., Keidar, I., Malkhi, D.: Failure detectors in omission failure environments. Technical Report TR96-1608, Cornell University, Computer Science Department (September 1996)Google Scholar
  9. 9.
    Dolev, D., Friedmann, R., Keidar, I., Malkhi, D.: Failure detectors in omission failure environments (brief announcement). In: 16th ACM Symposium on Principles of Distributed Computing, PODC (1997)Google Scholar
  10. 10.
    Dwork, C., Lynch, N.A., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)MathSciNetGoogle Scholar
  11. 11.
    Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)zbMATHMathSciNetGoogle Scholar
  12. 12.
    Hadzilacos, V.: Issues of Fault Tolerance in Concurrent Computations. PhD thesis, Harvard University, also published as Technical Report TR11-84 (1984)Google Scholar
  13. 13.
    Liu, Z., Joseph, M.: Specification and verification of fault-tolerance, timing and scheduling. ACM Transactions on Programming Languages and Systems 21(1), 46–89 (1999)CrossRefGoogle Scholar
  14. 14.
    Mostéfaoui, A., Mourgaya, E., Raynal, M.: Asynchronous implementation of failure detectors. In: Dependable Systems and Networks (DSN), pp. 351–360. IEEE Computer Society, Los Alamitos (2003)Google Scholar
  15. 15.
    Nestmann, U., Fuzzati, R.: Unreliable failure detectors via operational semantics. In: Saraswat, V.A. (ed.) ASIAN 2003. LNCS, vol. 2896, pp. 54–71. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  16. 16.
    Perry, K.J., Toueg, S.: Distributed agreement in the presence of processor and communication faults. IEEE Transactions on Software Engineering 12(3), 477–482 (1986)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Carole Delporte-Gallet
    • 1
  • Hugues Fauconnier
    • 2
  • Felix C. Freiling
    • 3
  1. 1.Institut d’électronique et d’informatique Gaspard-Monge (IGM)Marne-la-ValléeFrance
  2. 2.Laboratoire d’Informatique Algorithmique, Fondements et Applications (LIAFA)University Paris VIIFrance
  3. 3.Laboratory for Dependable Distributed SystemsRWTH Aachen UniversityGermany

Personalised recommendations