Faster-than Relation for Asynchronous Processes

摘要

Abstract. This paper introduces a novel (bi)simulation.based faster.than preorder which relates asynchronous processes with respect to their worst-case timing behavior. The studies are conducted for a conservative extension of the process algebra CCS, called TACS, which permits the specification of maximal time bounds of actions. TACS complements work in plain process algebras which compares asynchronous processes with respect to their functional reactive behavior only, and in timed process algebras which focus on analyzing synchronous processes. The most unusual contribution of this paper is in showing that the proposed faster.than preorder coincides with two other and at least equally appealing preorders, one of which considers the absolute times at which actions occur in system runs. The paper also develops the semantic theory of TACS: it characterizes the largest precongruence contained in the faster.than preorder, presents an axiomatization in a fragment of the algebra, and investigates a corresponding weak faster.than preorder. A small example relating two implementations of a simple storage system testifies to the practical utility of the new theory.