On synchronous and asynchronous interaction in distributed systems. (English) Zbl 1173.68585
Ochmański, Edward (ed.) et al., Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85237-7/pbk). Lecture Notes in Computer Science 5162, 16-35 (2008).
Summary: When considering distributed systems, it is a central issue how to deal with interactions between components. In this paper, we investigate the paradigms of synchronous and asynchronous interaction in the context of distributed systems. We investigate to what extent or under which conditions synchronous interaction is a valid concept for specification and implementation of such systems. We choose Petri nets as our system model and consider different notions of distribution by associating locations to elements of nets. First, we investigate the concept of simultaneity which is inherent in the semantics of Petri nets when transitions have multiple input places. We assume that tokens may only be taken instantaneously by transitions on the same location. We exhibit a hierarchy of ‘asynchronous’ Petri net classes by different assumptions on possible distributions. Alternatively, we assume that the synchronisations specified in a Petri net are crucial system properties. Hence transitions and their preplaces may no longer placed on separate locations. We then answer the question which systems may be implemented in a distributed way without restricting concurrency, assuming that locations are inherently sequential. It turns out that in both settings we find semi-structural properties of Petri nets describing exactly the problematic situations for interactions in distributed systems.
For the entire collection see [Zbl 1154.68021].
For the entire collection see [Zbl 1154.68021].
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
References:
| [1] | van der Aalst, W. M.P.; Kindler, E.; Desel, J., Beyond asymmetric choice: A note on some extensions, Petri Net Newsletter, 55, 3-13 (1998) |
| [2] | Best, E.; Brauer, W.; Reisig, W.; Rozenberg, G., Structure theory of Petri nets: The free choice hiatus, Advances in Petri Nets 1986, 168-206 (1987), Heidelberg: Springer, Heidelberg · Zbl 0633.68055 |
| [3] | Best, E.; Shields, M. W.; Ausiello, G.; Protasi, M., Some equivalence results for free choice nets and simple nets and on the periodicity of live free choice nets, Proceedings 8th Colloquium on Trees in Algebra and Programming (CAAP 1983), 141-154 (1983), Heidelberg: Springer, Heidelberg · Zbl 0531.68015 |
| [4] | de Boer, F. S.; Palamidessi, C.; Baeten, J. C.M.; Groote, J. F., Embedding as a tool for language comparison: On the CSP hierarchy, (CONCUR 1991), 127-141 (1991), Heidelberg: Springer, Heidelberg |
| [5] | Bougé, L., On the existence of symmetric algorithms to find leaders in networks of communicating sequential processes, Acta Informatica, 25, 2, 179-201 (1988) · Zbl 0621.68011 · doi:10.1007/BF02737102 |
| [6] | van Glabbeek, R.J., Goltz, U., Schicke, J.-W.: Symmetric and asymmetric asynchronous interaction. Technical Report 2008-03, TU Braunschweig. Extended abstract in Proceedings 1st Interaction and Concurrency Experience (ICE 2008) on Synchronous and Asynchronous Interactions in Concurrent Distributed Systems, to appear in Electronic Notes in Theoretical Computer Science. Elsevier, Amsterdam (2008) · Zbl 1291.68291 |
| [7] | van Glabbeek, R.J., Goltz, U., Schicke, J.-W.: On synchronous and asynchronous interaction in distributed systems. Technical Report 2008-04, TU Braunschweig (2008) · Zbl 1173.68585 |
| [8] | Gorla, D.; Aceto, L.; Ingólfsdóttir, A., On the Relative Expressive Power of Asynchronous Communication Primitives, Foundations of Software Science and Computation Structures, 47-62 (2006), Heidelberg: Springer, Heidelberg · Zbl 1180.68190 · doi:10.1007/11690634_4 |
| [9] | Hopkins, R. P.; Rozenberg, G., Distributable nets, Advances in Petri Nets 1991, 161-187 (1991), Heidelberg: Springer, Heidelberg · doi:10.1007/BFb0019974 |
| [10] | Lamport, L., Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, 21, 7, 558-565 (1978) · Zbl 0378.68027 · doi:10.1145/359545.359563 |
| [11] | Lamport, L., Arbitration-free synchronization, Distributed Computing, 16, 2-3, 219-237 (2003) · Zbl 1448.68138 · doi:10.1007/s00446-002-0076-2 |
| [12] | Lynch, N., Distributed Algorithms (1996), San Francisco: Morgan Kaufmann Publishers, San Francisco · Zbl 0877.68061 |
| [13] | Nestmann, U., What is a ‘good’ encoding of guarded choice?, Information and Computation, 156, 287-319 (2000) · Zbl 1046.68625 · doi:10.1006/inco.1999.2822 |
| [14] | Olderog, E.-R.; Hoare, C. A.R., Specification-oriented semantics for communicating processes, Acta Informatica, 23, 9-66 (1986) · Zbl 0569.68019 · doi:10.1007/BF00268075 |
| [15] | Palamidessi, C.: Comparing the expressive power of the synchronous and the asynchronous pi-calculus. In: Conference Record of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 1997), pp. 256-265. ACM Press, New York (1997) |
| [16] | Reisig, W., Deterministic buffer synchronization of sequential processes, Acta Informatica, 18, 115-134 (1982) · Zbl 0478.68023 · doi:10.1007/BF00264434 |
| [17] | Selinger, P.; Mazurkiewicz, A.; Winkowski, J., First-order axioms for asynchrony, (CONCUR 1997), 376-390 (1997), Heidelberg: Springer, Heidelberg · Zbl 1512.68098 |
| [18] | Taubner, D., Zur verteilten Implementierung von Petrinetzen, Informationstechnik, 30, 5, 357-370 (1988) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
