© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Using Probability to Reason about Soft Deadlines
Andy King and Jeremy Bryans
Technical Report 13-98, Computing Laboratory, August 1998 Presented at the International Workshop on Constraint Programming for Time Critical Applications and Multi-Agent Systems, Nice, France.Abstract
Soft deadlines are significant in systems in which a bound on the response time is important, but the failure to meet the response time is not a disaster. Soft deadlines occur, for example, in telephony and switching networks. We investigate how to put probabilistic bounds on the time-complexity of a concurrent logic program by combining (on-line) profiling with an (off-line) probabilistic complexity analysis. The profiling collects information on the likelihood of case selection and the analysis uses this information to infer the probability of an agent terminating within (unknown variable k)$ steps. Although the approach does not reason about synchronization, we believe that its simplicity and good (essentially quadratic) complexity mean that it is a promising first step in reasoning about soft deadlines.
Download publication 45 kbytesBibtex Record
@techreport{601, author = {Andy King and Jeremy Bryans}, title = {Using {P}robability to {R}eason about {S}oft {D}eadlines}, month = {August}, year = {1998}, pages = {182-196}, keywords = {determinacy analysis, Craig interpolants}, note = {Presented at the International Workshop on Constraint Programming for Time Critical Applications and Multi-Agent Systems, Nice, France}, doi = {}, url = {http://www.cs.kent.ac.uk/pubs/1998/601}, institution = {Computing Laboratory}, number = {13-98}, }