A Faster-than Relation for Asynchronous Processes
INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
Pagination or Media Count:
Abstract. This paper introduces a novel bisimulationbased fasterthan 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 fasterthan 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 fasterthan preorder, presents an axiomatization in a fragment of the algebra, and investigates a corresponding weak fasterthan preorder. A small example relating two implementations of a simple storage system testifies to the practical utility of the new theory.
- Computer Programming and Software
- Computer Hardware