Efficiency of token-passing MUTEX-solutions – some experiments. (English) Zbl 1510.68052
Desel, Jörg (ed.) et al., Application and theory of Petri nets 1998. 19th international conference, ICATPN’98, Lisbon, Portugal, June 22–26, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1420, 185-204 (1998).
Summary: A formerly developed approach for comparing the efficiency of asynchronous systems is applied to some token-passing systems (one of them presumably new) that solve the MUTEX-problem. While the original approach compares systems, we also quantify the efficiency by a number and used our tool FastAsy to assess the effects the number of users and the delay in their communication links have. Finally, some new results allowed us to prove correctness of the solutions with FastAsy.
For the entire collection see [Zbl 1499.68015].
For the entire collection see [Zbl 1499.68015].
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
| 68Q45 | Formal languages and automata |
Software:
FastAsyReferences:
| [1] | S. Christensen, N.D. Hansen. Coloured Petri nets extended with place capacities, test arcs, and inhibitor arcs. In M. Ajmone-Marsan, editor, Applications and Theory of Petri Nets 1993, LNCS 691, 186-205. Springer, 1993. |
| [2] | E.W. Dijkstra. Invariance and non-determinacy. In R. Hoare, C. A and J.C. Sheperdson, editors, Mathematical Logic and Programming Languages, 157-165. Prentice-Hall, 1985. |
| [3] | R. De Nicola, M.C.B. Hennessy. Testing equivalence for processes. Theoret Comput. Sci., 34:83-133, 1984. · Zbl 0985.68518 · doi:10.1016/0304-3975(84)90113-0 |
| [4] | R. Janicki, M. Koutny. Semantics of inhibitor nets. Information and Computation, 123:1-16, 1995. · Zbl 1096.68678 · doi:10.1006/inco.1995.1153 |
| [5] | L. Jenner, W. Vogler. Fast asynchronous systems in dense time. In F. Meyer auf der Heide and B. Monien, editors, Automata, Languages and Programming ICALP’96, Lect. Notes Comp. Sci. 1099, 75-86. Springer, 1996. · Zbl 1046.68623 |
| [6] | E. Kindler, R. Walter. Message passing mutex. In J. Desel, editor, Structures in Concurrency Theory, Worksh. in Computing, 205-219. Springer, 1995. |
| [7] | E. Kindler, R. Walter. Mutex needs fairness. Inf. Proc. Letter, 62:31-39, 1997. · Zbl 1336.68182 · doi:10.1016/S0020-0190(97)00033-1 |
| [8] | N. Lynch, F. Vaandrager. Forward and backward simulations I: Untimed systems. Information and Computation, 121:214-233, 1995. · Zbl 0834.68123 · doi:10.1006/inco.1995.1134 |
| [9] | N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Francisco, 1996. · Zbl 0877.68061 |
| [10] | U. Montanari, F. Rossi. Contextual nets. Acta Informatica, 32:545-596, 1995. · Zbl 0835.68084 |
| [11] | PEP Homepage. http://www.informatik.uni-hildesheim.de/pep/. |
| [12] | M. Raynal. Algorithms for Mutual Exclusion. North Oxford Academic, 1986. · Zbl 0662.68002 |
| [13] | P.H. Starke. Analyse von Petri-Netz-Modellen. Teubner, 1990. · Zbl 0724.68002 |
| [14] | W. Vogler. Timed testing of concurrent systems. Information and Computation, 121:149-171, 1995. · Zbl 0833.68048 · doi:10.1006/inco.1995.1130 |
| [15] | W. Vogler. Faster asynchronous systems. In I. Lee and S. Smolka, editors, CONCUR 95, Lect. Notes Comp. Sci. 962, 299-312. Springer, 1995. Full version as Report Nr. 317, Inst. f. Mathematik, Univ. Augsburg, 1995. |
| [16] | W. Vogler. Efficiency of asynchronous systems and read arcs in Petri nets. In P. Degano, R. Gorrieri, and A. Marchetti-Spaccamela, editors, ICALP 97, Lect. Notes Comp. Sci. 1256, 538-548. Springer, 1997. Full version as technical report Nr. 352, Inst. f. Mathematik, Univ. Augsburg, 1996. · Zbl 1401.68235 |
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.
