Skip to main content

Using Probability to Reason about Soft Deadlines

King, Andy, Bryans, Jeremy W. (1998) Using Probability to Reason about Soft Deadlines. University of Kent, School of Computing, 7 pp. (KAR id:21616)

Language: English
Download (218kB) Preview


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 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.

Item Type: Research report (external)
Additional information: Presented at the International Workshop on Constraint Programming for Time Critical Applications and Multi-Agent Systems, Nice, France
Uncontrolled keywords: deadlines, agents, profiling, termination.
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Sciences > School of Computing > Theoretical Computing Group
Depositing User: Andy King
Date Deposited: 22 Aug 2009 23:22 UTC
Last Modified: 15 Feb 2020 04:02 UTC
Resource URI: (The current URI for this page, for reference purposes)
King, Andy:
  • Depositors only (login required):


Downloads per month over past year