NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Priority in Process AlgebrasThis paper surveys the semantic ramifications of extending traditional process algebras with notions of priority that allow for some transitions to be given precedence over others. These enriched formalisms allow one to model system features such as interrupts, prioritized choice, or real-time behavior. Approaches to priority in process algebras can be classified according to whether the induced notion of preemption on transitions is global or local and whether priorities are static or dynamic. Early work in the area concentrated on global pre-emption and static priorities and led to formalisms for modeling interrupts and aspects of real-time, such as maximal progress, in centralized computing environments. More recent research has investigated localized notions of pre-emption in which the distribution of systems is taken into account, as well as dynamic priority approaches, i.e., those where priority values may change as systems evolve. The latter allows one to model behavioral phenomena such as scheduling algorithms and also enables the efficient encoding of real-time semantics. Technically, this paper studies the different models of priorities by presenting extensions of Milner's Calculus of Communicating Systems (CCS) with static and dynamic priority as well as with notions of global and local pre- emption. In each case the operational semantics of CCS is modified appropriately, behavioral theories based on strong and weak bisimulation are given, and related approaches for different process-algebraic settings are discussed.
Document ID
19990021253
Acquisition Source
Langley Research Center
Document Type
Preprint (Draft being sent to journal)
Authors
Cleaveland, Rance
(Institute for Computer Applications in Science and Engineering Hampton, VA United States)
Luettgen, Gerald
(Institute for Computer Applications in Science and Engineering Hampton, VA United States)
Natarajan, V.
(International Business Machines Corp. Research Triangle Park, NC United States)
Date Acquired
September 6, 2013
Publication Date
January 1, 1999
Subject Category
Computer Programming And Software
Report/Patent Number
NASA/CR-1999-208979
NAS 1.26:208979
ICASE-99-3
Funding Number(s)
CONTRACT_GRANT: NSF CCR-94-02807
PROJECT: RTOP 505-90-52-01
CONTRACT_GRANT: NSF INT-96-03441
CONTRACT_GRANT: NAS1-97046
CONTRACT_GRANT: F49620-95-I-0508
CONTRACT_GRANT: NSF CCR-92-57963
CONTRACT_GRANT: NSF CCR-95-05662
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available