PERFORMANCE PREORDER AND COMPETITIVE EQUIVALENCE

A preorder based on execution speed, called performance preorder, is i ntroduced for a simple process algebra with durational actions. Two pr ocesses E and F are related -E box with right side missing(p) F- if th ey have the same functionality (in this case, we have chosen strong bi simulation equivalence) and E is at least as fast as F. Hence, this pr eorder supports the stepwise refinement ''from specification to implem entation'' by increasing efficiency while retaining the same functiona lity. 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. Both performance preorder and the induced equivalence, called competitive equivalence, are provi ded with sound and complete axiomatizations for finite agents.