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.