Using Probability to Reason about Soft Deadlines

King, Andy and Bryans, Jeremy (1998) Using Probability to Reason about Soft Deadlines. University of Kent, School of Computing, 7 pp. (Full text available)

PDF
Download (133kB)
[img]
Preview

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 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 > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User: Andy King
Date Deposited: 22 Aug 2009 23:22
Last Modified: 13 Dec 2013 12:28
Resource URI: http://kar.kent.ac.uk/id/eprint/21616 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year