School of Computing

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 kbytes

Bibtex 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},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014