Paper Info
Title
An Algebra of Synchronous Scheduling Interfaces
Abstract
In this paper we propose an algebra of synchronous scheduling interfaces which combines the expressiveness of Boolean algebra for logical and functional behaviour with the min-max-plus arithmetic for quantifying the non-functional aspects of synchronous interfaces. The interface theory arises from a realisability interpretation of intuitionistic modal logic (also known as Curry-Howard-Isomorphism or propositions-as-types principle). The resulting algebra of interface types aims to provide a general setting for specifying type-directed and compositional analyses of worst-case scheduling bounds. It covers synchronous control flow under concurrent, multi-processing or multi-threading execution and permits precise statements about exactness and coverage of the analyses supporting a variety of abstractions. The paper illustrates the expressiveness of the algebra by way of some examples taken from network flow problems, shortest-path, task scheduling and worst-case reaction times in synchronous programming.
Year
DOI
Venue
2010
10.4204/EPTCS.46.3
FIT
Keywords
Field
DocType
shortest path,control flow,reaction time,modal logic,network flow,programming language,boolean algebra
Logical conjunction,Abstraction,Programming language,Scheduling (computing),Computer science,Theoretical computer science,Expressivity,Flow network,Synchronous control,Algebra,Algorithm,Modal logic,Boolean algebra
Journal
ISSN
Citations 
PageRank 
EPTCS 46, 2011, pp. 28-48
0
0.34
References 
Authors
10
1
Name
Order
Citations
PageRank
Michael Mendler131434.60