Communication Dualism in Distributed Systems with Petri Net Interpretation

• Autorzy: Chrobot S. , Daszczuk W.

Warianty tytułu

PL

Dualizm komunikacyjny w systemach rozproszonych z interpretacją w sieci Petri

• Języki publikacji: EN

Abstrakty

EN

In the paper notion of communication dualism id formalized and explained in Petri net interpretation. We considcr communication dualism a basic property of communication in distributcd systems. The formalization is done in the Integrated Model of Distributed Systems (IMDS) where synchronous communication, as wcll as asynchronous message-passing and variable-sharing are modeled in a common framework. In the light of this property, communication in distributed systems can be seen as a two-dimensional phenomenon with passing being its spatial dimension and sharing its temporal dimension. Any distributed system can be modeled as a composition of message-passes asynchronous processes or as a composition of variable-sharing asynchronous processes. A method of automatic process extraction in Petri net interpretation of IMDS is presented.

PL

W artykule zdefiniowano pojęcie dualizmu komunikacyjnego oraz przedstawiono jego interpretację w sieci Petri. Dualizm komunikacyjny jest uznawany przez autorów za fundamentalną własność komunikacji w systemach rozproszonych. Formalizację przeprowadzono przy użyciu Zintegrowanego Modelu Systemów Rozproszonych (IMDS), w którym wprowadzono elementy pamięciowe rezydujące w węzłach i elementy przesyłane adresowane do węzłów. Podstawowym elementem dynamicznym jest akcja polegająca na spotkaniu elementu pamięciowego z elementem przesyłanym i wygenerowanie na ich miejsce zbioru nowych elementów pamięciowych i przesyłanych. Formalizm IMDS w jednolitej strukturze obejmuje komunikację synchroniczną i asynchroniczną, zarówno opartą o przesyłanie meldunków jak i o współdzielenie zmiennych. Z punktu widzenia dualizmu komunikacyjnego komunikacja jest dwuwymiarowym zjawiskiem, w którym przesyłanie meldunków odbywa się w wymiarze przestrzennym a współdzielenie zmiennych w wymiarze czasowym. Każdy system rozproszony może być przedstawiony jako złożenie asynchronicznych procesów przesyłających komunikaty lub jako złożenie asynchronicznych procesów współdzielących zmienne. Przedstawiono dwie kanoniczne dekompozycje systemów na procesy rezydentne z jednej strony i procesy podróżne z drugiej. W dekompozycji na procesy rezydentne wartości zmiennych są wewnętrznym sposobem komunikacji w procesie, a przesyłanie meldunków jest komunikacją międzyprocesową. W dekompozycji na procesy podróżne meldunki stanowią wewnętrzną komunikację w procesie, a współdzielenie zmiennych jest komunikacją międzyprocesową. Wprowadzono interpretację elementów pamięciowych i przesyłanych jako miejsc w sieci Petri, wykonania akcji jako odpalenia przejścia w sieci Petri, oraz interpretację ciągu odpaleń przejść poprzez miejsca określonego typu jako procesów. Przedstawiono sposób powoływania i zakańczania procesów. Podano sposób automatycznego wyodrębnienia procesów rezydentnych i podróżnych systemu w interpretacji IMDS przy pomocy sieci Petri.

Słowa kluczowe

EN

communication dualism; concurrency; concurrency modeling; Petri nets; Petri net modeling; system decomposition

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2006
• Tom: Vol. 18, nr 4
• Strony: 261--278
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Chrobot S.

autor

Daszczuk W.

• Institute of Computer Science Warsaw University of Technology,

Bibliografia

• [1] Benton, N.,Cardelli, L., Foumel, C. (2002): Modem concurrency Abstractions for C-Sharp, Proc. Object Oriented Programming.ng ECOOP'02, Jun. 2002, LNCS 2374, Springer-Verlag, pp.415-440
• [2] Boudol, G. (1992): Asynchrony in the pi-calculus Technical Report RR-1702, INRIA-SophiaAntipolis
• [3] Chrobot, S., Stras, A., Stras, R. (1998): ARS - Ań Integrated Package for Shared-Variable and Message-Passing Computations in Object-Based Systems. Concurrency - Practice and Experience, Vol. 10(15), pp.1271-1290
• [4] Chrobot, S. (2000a): The Termination Problem in the Dud Versions of Distributed Systems. Proc. PDPTA'2000, June, 2000, Las Vegas.
• [5] Chrobot, S. (2000b): Sharing Variables in Distributed Memory. Fundamenta Informatice, vol.44,pp. 63-81.
• [6] Chrobot, S. (2001): The Anatomy of Deadlock, Proc. International Conference on Parallel Processing, September 3-7, 2001, Valencia, Spain, pp.13-24.
• [7] Chrobot, S. (2002): Modelling Communication in Distributed Systems, Proc. International Conference on Parallel Computing in Electrical Engineering PARELEC'02, pp.55-60.
• [8] Chrobot, S. (2004): Introducing Yariable Sharing to Process Calculi, Proc. International Conference on Parallel Computing in Electrical Engineering PARELEC'04 Dresden, Germany, pp.99-104
• [9] Clarke, E. M, Grumberg, O., Peled, D. A. (1999): Model Checking, Cambridge, MA: MIT Press
• [10] Fournet, C., Gonthier, G. (1996): The Reflexive Chemical Abstract Machinę and the Join Calculus, Proc. Principles of Programming Languages POPL'96, ACM, Jan 1996, pp.372-385
• [11] Fournet, C., Gonthier, G. (2000): The Join Calculus: a Language for Distributed Mobile Programming, Applied Semantics, International Summer School, ASSPEM 2000, Caminha, Portugal, 9-15 Sept 2000, Advanced Lectures, pp.268-332
• [12] Fournet, C., Gonthier, G., Levy, J-J., Maranget, L., Remy, D. (1996): A Calculus of Mobile Agents. CONCUR'96, LNCS 1119, Springer-Verlag, pp. 406-421.
• [13] Le Fessant, F., Maranget, L. (1998): Compiling Join Patterns, Proc. 3rd international work-shop on High-Level Concurrent Languages HLCL'98, Nice, Sept 1998, Electronic Notes in Computer Science, vol. 16(3), Elsevier 1999
• [14] Hoare, C. A. R. (1978): Communicating sequential processes. Comm. ACM, 21(8), 1978, pp. 666-677.
• [15] Honda, K., Tokoro, M. (1991): An Object Calculus for Asynchronous Communication, Proc. . Object Oriented Programming ECOOP'91, LNCS 512, Springer-Verlag, pp.133-147
• [16] Lauer, H. C., Needham, R, M. (1978): On Duality of Operating System Structures. Proc. Second International Symposium on Operating Systems, IRIA, Oct 1978. Reprinted in Operating System Review, Vol. 13. No. 2. (1979) pp.3-19.
• [17] Lynch, N., A. (1996) Distributed Algorithms, San Francisco, CA: Morgan Kaufman Publishers
• [18] Milner, R. (1982): A Calculus of Communicating Systems. New York: Springer-Verlag
• [19] Milner, R. (1989): Communication and Concurrency, Prentice Hall
• [20] Milner, R., Parrow, J., Walker, D. (1992): A Calculus of Mobile Processes, Parts 1-2. Information and Computation, 100(1): pp.1-77
• [21] Parrow, J. (2000): Ań Introduction to the n Calculus, Chapter 8 in J. Bergstra, A. Ponse, and S. Smółka (eds.): Handbook of Process Algebra, Elsevier, pp.479-543
• [22] Pierce, B. C., Turner, D. N. (1994): Concurrent Objects in a Process Calculus, Proc. Theory and Practice of Parallel Programming TPPP, Sendai, Japan, Nov 1994, LNCS 907, 1995, Springer-Verlag, pp. 187-215
• [23] Pierce, B. C., Turner, D. N. (2000): Pict: A programming Language Basedon the Calculus. In Plotkin, G., Stirling, C., Tofte, M. (eds.), Proof, Language and Interaction: Essays in Honour of Robin Milner, MIT press, (2000), pp.455-494. Available also as Technical Report CSCI 476, Indiana Universiry, (1997).
• [24] Sewell, P., Wojciechowski, P. T., Pierce, B. C. (1999): Location independent Communication for Mobile Agents: a Two-Level Architecture, Technical Report 462, University of Cambridge
• [25] Wojciechowski, P. T., Sewell, P. (2000): Nomadic Pict: Language and Infrastructure Design for Mobile Agents, IEEE Concurrency 8(2), Apr 2000, pp.42-52