Seminarium
Systemy Rozproszone
                                     
Tolerancja Uszkodzeń - komunikacja grupowa.
Andrzej Marek Machnacz                                                  D.Grzegorski
Streszczenie.
Wraz ze wzrostem postępu pojawiło się nowe zapotrzebowanie na systemy rozproszone (distributed systems) umożliwiające korzystanie, dzięki szybkim łączom komunikacyjnym, z niewyczerpanych rozproszonych zasobów infrastruktury sieciowej  . Współcześnie ich zakres zastosowań jest stosunkowo rozbudowany  i obejmuje systemy baz danych, systemy kontroli lotów, automatykę przemysłową, medyczne systemy monitorujące, systemy podtrzymywania życia, aplikacje bankowe i giełdowe oraz wiele innych. 

W związku z rosnącymi wymaganiami dotyczącymi niezawodności (reliability) systemów pracujących w środowisku rozproszonym podjęto próbę budowy systemów tolerujących uszkodzenia (fault-tolerant systems). Obecnie na rynku jest wiele takich systemów, które różnią się przede wszystkim rodzajem komponentów systemu odpornych na błędy, czy też stopniem tolerancji uszkodzeń oraz sposobem osiągania niezawodności. W ten sposób mamy do czynienia z tolerancją uszkodzeń węzłów sieci (komputery, procesy) lub też z tolerancją uszkodzeń łącza komunikacyjnego. Część systemów zakłada jedynie występowanie uszkodzeń przejściowych (transient failures), a inne uszkodzeń trwałych, permanentnych (crash failures). Są też takie, które radzą sobie z oboma rodzajami uszkodzeń. Istnieją również systemy tolerujące uszkodzenia, które akceptują nawet wielokrotny podział sieci na partycje w wyniku awarii. Niektóre z systemów zapewniają niezawodność poprzez rozszerzenie warstwy aplikacji o mechanizmy zapewniające poprawną pracę w systemie rozproszonym nawet w przypadku wystąpienia awarii. W takim rozwiązaniu to warstwa aplikacji przejmuje na siebie odpowiedzialność za tolerancję uszkodzeń. Jeszcze inne systemy stosują warstwy pośrednie wykorzystujące odpowiednie protokoły tolerancji uszkodzeń, które umożliwiają odporne na uszkodzenia rozproszone wykonywanie procesów. 

Tolerancja uszkodzeń jest stosunkowo obszerną dziedziną i obejmuje zagadnienia związane z wycofywaniem operacji (rollback), odzyskiwaniem danych (recovery), maskowaniem i ograniczaniem skutków uszkodzeń (fault masking, fault containing), a także z lokalnym usuwaniem uszkodzeń (fault local mending), z protokołami rozproszonego głosowania (voting protocols) i zatwierdzania transakcji (commit protocols) oraz z algorytmami samo-stabilizującymi się (self-stabilization algorithms). W ostatnich latach bardzo duży nacisk został położony na badania nad niezawodną komunikacją grupową (reliable group communications), czego wynikiem jest szeroki zakres zastosowań.  
 
Seminarium będzie wprowadzeniem do systemów tolerujacych uszkodzenia, a w szczególności systemów niezawodnej komunikacji grupowej. Zostaną przedstawione problemy pojawiające się w trakcie konstrukcji takich systemów, a także przykładowa implementacja jednego z pierwszych systemów niezawodnej komunikacji grupowej (system Isis).
 

 Literatura:
  • D.A. Agarwal, P.M. Melliar-Smith, L.E. Moser, „Totem: A protocol for Message Ordering in a Wide Area Network”, In Proc. 1st ISMM International Conference on Computer Communications and Networks, 1992.
  • Y. Amir, D. Dolev, S. Kramer, D. Malki, „Transis: A Communication Sub-System for High Availability”, In 22nd Annual International Symposium on Fault-Tolerant Computing, 1992, pp.76-84.
  • Y. Amir, D. Dolev, S. Kramer, D. Malki, „Exploiting LAN Broadcast for High Availability Communication Services”, In 6th Israeli Conference on Computer Systems and Software Engineering, 1992.
  • Y. Amir, D. Dolev, S. Kramer, D. Malki, „A Highly Available Application in the Transis Environment”, Institute of Computer Science, The Hebrew University of Jerusalem, Israel.
  • Ö. Babaoglu, R. Davoli, L. Giachini, M.Baker, „Relacs: A Communications Infrastructure for Constructing Reliable Applications in Large-Scale Distributed Systems”, In Proc. 28th International Conference on System Sciences, 1995, pp.612-621.
  • K. Birman, T. Joseph, „Reliable Comunication in the Presence of Failures”, ACM Trans. Comput. Syst., vol. 5, no.1, pp.47-76, February 1987.
  • K. Birman, R. Cooper, T. Joseph, K. Marzullo, M. Makpangou, K. Kane, F. Schmuck, M. Wood, „The ISIS System Manual”, Department of  Computer Science, Cornell University, September 90.
  • K. Birman, R. Cooper, „The ISIS Project: Real experience with a fault tolerant programming system”, Department of  Computer Science, Cornell University , Ithaca.
  • K. Birman, „ISIS: A System for Fault-Tolerant Distributed Computing”, Department of  Computer Science, Cornell University, Ithaca, NY April 1986.
  • K. Birman, A. Abbadi, W. Dietrich, T. Joseph, T. Raeuchle „A Overview of the Isis Project”, Department of  Computer Science, Cornell University, Ithaca, NY October 1984.
  • J. Brzeziński, M. Szychowiak, „Systemy Rozproszone Tolerujące Uszkodzenia”, Instytut Informatyki Politechniki Poznańskiej (POLMAN 97).
  • T.D. Chandra, S. Toueg, „Unreliable Failure Detectors for Reliable Distributed Systems”, In Proc. 10th ACM Symp. Principles of Distributed Computing, ACM Press, 1991, pp.325-340.
  • J. M. Chang, N. Maxemchuck, „Reliable Broadcast Protocols”, ACM Trans. Comput. Syst., vol. 2, no. 3, pp.251-273, August 1984.
  • P. Felber, R. Guerraoui, „Group programming: An Object Oriented Approach”, In Proceedings of the International Conference on Technology of Object Oriented Languages and Systems (TOOLS), 1995.
  • M. Fisher, N. Lynch, M. Peterson, „Impossibility of Distributed Consensus with One Faulty Process”, In Journal of ACM, vol. 32, 1985, pp.374-382.
  • R. Guerraoui, A. Schiper, „Fault-Tolerance by Replication in Distributed Systems”, EPFL, Lausanne.
  • C.P. Malloth, „Conception and Implementation of a Toolkit for building Fault-Tolerant Distributed Applications in Lange Scale networks”, PhD. Thesis, EPFL, Lausanne 1996.
  • Ch. Malloth, P. Felber, A. Schiper, U. Wilhelm, „Phoenix - A Toolkit for Building Fault-Tolerant Distributed Applications in Large Scale”, EPFL,  Lausanne.
  • R. Guerraoui, A. Schiper, „? - Accurate Failure Detectors. In 10th International Workshop on Distributed Algorithms preceedings (WDAG-10). Springer Verlag, October 1996.
  • R. Guerraoui, A. Schiper, „Consensus Service: a modular approach for building agreement protocol in distributed systems”, EPFL, Lausanne.
  • J.K. Outerhout, „Tcl and the Tk Toolkit”, Addison-Wesley, 1994.
  • L.L. Peterson, N.C. Buchholz, R.D. Schlichting, „Preserving and Using Cpntext Information in Interprocess Communication”, ACMTrans. On Computer Systems, vol. 7, #3, 1989, pp.217-246.
  • A.S. Tanenbaum, M.F. Kaashoek, „Group Communication in the Amoeba Distributed Operating System”, Proceedings of 11th IEEE Intern. Conference on Distr. Comp. Sys., Arlington, 1991, pp. 882-891.
  • G. Tel, „Introduction to Distribution Algorithms”,  Cambridge University Press 1994.
  • S. Toueg, „On Consensus and Related Problems in Asynchronous Distributed Systems”, Department of  Computer Science, Cornell University, Ithaca.
  • S. Toueg, „Consensus and Related Problems”, Department of  Computer Science, Cornell University, Ithaca, 1997.
  • R. van Renesse, K. Birman, R. Cooper, B. Glade, P. Stepherson, „The Horus System”, In Birman & van Renesse: Reliable Distributed Computing with the Isis Toolkit, IEEE Computer Society Press, 1993, pp.133-147.
  • R. van Renesse, K. Birman, „Ptotocol Composition in Horus”, Department of  Computer Science, Cornell University, March 29, 1995.
  • P. Verissimo, L. Rodrigues, J. Rufino, „TheAtomic Multicast Protocol (Amp)”, In D. Powell, „Delta-4: A Generic Architecture for Dependable Distributed Computing”, Springer-Verlag, 1991, pp.267-294.
  • B. Whetten, T. Montgomery, S. Kaplan, „A High Performance Totally Ordered Multicast Protocol”, In Lecture Notes in Computer Science #938, Springer-Verlag, 1994, pp.33-57.