Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm a programmer and I know this must be an elementary question. I think I could work out an algorithm of my own, but I'd probably get it wrong.

I have a data feed that describes the status of one or more scheduled events (up to about 12 simultaneous events). This feed is intrinsically temperamental and can fail at several levels, but when it fails it typically affects only one event or it affects all of them at the same time. I am building a monitoring system to check the feed for out-of-the-ordinary update delays for these two scenarios.

I check for updates to the feed every 2 minutes. On average the information about each event changes every 6 minutes, but it's not unusual for an event to remain unchanged for 25 minutes. For an individual event to raise an alarm, it would not have updated for 30 minutes.

However, if 12 simultaneous events don't update for 2 or 4 minutes (that's a guestimate, I'm not sure which), it may be a sign of major server issues and should trigger an alarm immediately. If there are 4 simultaneous events, the alarm should trigger later (somewhere between 4 minutes and 30 minutes).

So as the sample size grows or shrinks, how would I determine the delay time that triggers the alarm?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

To answer this, we also need to know the rate with which these types of failures occur. The more often a complete failure occurs, the shorter the delay time should be. If the rate at which complete failures occur is much lower than the rate at at which single-event failures occur, the appropriate delay time may even be longer than the one for individual events: The appropriate delay time is a function both of the number of events and of the rate of failure, and that rate is probably different for the single-event failure type and the complete failure type.

For a quantitative treatment, let's say we have $n$ independent Poisson processes with identical parameter $\lambda$ (the events) and a further independent Poisson process with parameter $\mu$ (the complete failure). That is, on average there are $\lambda$ events of each event type per time unit and $\mu$ complete failures per time unit. Let's assume that a complete failure prevents all events from being registered until we notice and fix it, and let's say we want the alarm to be triggered when the probability of a complete failure having occurred reaches $p$.

Whenever we see an event, the probability of a complete failure having occurred is reset to $0$. If we then don't observe any events for a time $\tau$, then either no failure and no events occurred, or a failure occurred and no events occurred before the failure.

The time $t$ of the next occurrence for a Poisson process with parameter $\lambda$ has probability density function $\lambda\mathrm e^{-\lambda t}$, so the probability for no event to occur in the process by time $\tau$ is

$$ \int_\tau^\infty\lambda\mathrm e^{-\lambda t}\,\mathrm dt=\mathrm e^{-\lambda \tau}\;. $$

Thus, the probability for no failure to occur and no events to be observed by time $\tau$ is

$$P(\text{no failure}\land\text{no events observed})=\mathrm e^{-\mu \tau}\left(\mathrm e^{-\lambda \tau}\right)^n=\mathrm e^{-(\mu+n\lambda) \tau}\;.$$

The probability for a failure to occur and no events to be observed by time $\tau$ is a bit more involved. We have to integrate the probability $\mathrm e^{-n\lambda t}$ that no events have occurred by time $t$ with the probability density $\mu\mathrm e^{-\mu t}$ for a failure to occur at time $t$:

$$ P(\text{failure}\land\text{no events observed})=\int_0^\tau\mu\mathrm e^{-\mu t}\mathrm e^{-n\lambda t}\,\mathrm dt=\frac{\mu}{\mu+n\lambda}\left(1-\mathrm e^{-(\mu+n\lambda) \tau}\right)\;. $$

Thus the total probability for no events to be observed by time $\tau$ is

$$ P(\text{no events observed})=\mathrm e^{-(\mu+n\lambda) \tau}+\frac{\mu}{\mu+n\lambda}\left(1-\mathrm e^{-(\mu+n\lambda) \tau}\right)=\frac{\mu+n\lambda\mathrm e^{-(\mu+n\lambda) \tau}}{\mu+n\lambda}\;. $$

The conditional probability that no failure has occurred, given that no events were observed over time $\tau$, is the ratio of the probability of no failure and no events occurring by time $\tau$ and the total probability for no events to be observed:

$$ \begin{align} P(\text{no failure}\mid\text{no events observed}) &= \frac{P(\text{no failure}\land\text{no events observed})}{P(\text{no events observed})} \\ &= \mathrm e^{-(\mu+n\lambda) \tau}\Big/\frac{\mu+n\lambda\mathrm e^{-(\mu+n\lambda) \tau}}{\mu+n\lambda} \\ &= \frac{\mu+n\lambda}{\mu\mathrm e^{(\mu+n\lambda) \tau}+n\lambda}\;. \end{align} $$

As expected, this is $1$ for $\tau=0$ and goes to $0$ as $\tau\to\infty$.

To use this in your situation, you could measure the rate $\lambda$ at which events occur, the rate $\mu_1$ at which single-event failures occur and the rate $\mu_n$ at which complete failures occur. You're using a delay time $\tau_1=30s$ for single-event failures, and the probability $p_1$ of a single-event failure having occurred at which your currently implemented alarm goes off is

$$ p_1=1-\frac{\mu_1+\lambda}{\mu_1\mathrm e^{(\mu_1+\lambda)\tau_1}+\lambda}\;. $$

To get the alarm for complete failures to go off at the same failure probability $p_n=p_1$, you'd need to choose the delay time $\tau_n$ for complete failures to satisfy

$$ \frac{\mu_n+n\lambda}{\mu_n\mathrm e^{(\mu_n+n\lambda)\tau_n}+n\lambda}=1-p_n=1-p_1=\frac{\mu_1+\lambda}{\mu_1\mathrm e^{(\mu_1+\lambda)\tau_1}+\lambda}\;. $$

Solving for $\tau_n$ yields

$$ \tau_n=\frac1{\mu_n+n\lambda}\log\left(\frac1{\mu_n}\left(\frac{\mu_n+n\lambda}{\mu_1+\lambda}\left(\mu_1\mathrm e^{(\mu_1+\lambda)\tau_1}+\lambda\right)-n\lambda\right)\right)\;. $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.