×

Performance preorder: ordering processes with respect to speed. (English) Zbl 1193.68173

Wiedermann, Jiří (ed.) et al., Mathematical foundations of computer science 1995. 20th international symposium, MFCS ’95, Prague, Czech Republic, August 28-September 1, 1995. Proceedings. Berlin: Springer-Verlag (ISBN 3-540-60246-1). Lect. Notes Comput. Sci. 969, 444-453 (1995).
Summary: The theory of processes with durational actions is equipped here with a preorder based on execution speed, called performance preorder. Two processes \(P\) and \(Q\) are related if they are strong bisimilar (i.e., functional equivalent) and the first one is at least as fast as the second one. Hence, this preorder supports the stepwise refinement ‘from specification to implementation’ by increasing efficiency while retaining the same functionality. We show that the problem of finding faster implementations for a specification is connected to the problem of finding more distributed implementations of the same specification. This is an immediate consequence of the proof that the location preorder, which is based on a measure of distribution, implies the performance preorder.
For the entire collection see [Zbl 0847.00052].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI