Fault localization in distributed systems using invariant relationships

1. A computer implemented method for temporal ranking in invariant networks comprising the steps of:

considering an invariant network and a set of broken invariants in the invariant network;

assuming, for each time point inside a window W, that each metric with broken invariants is affected by a fault at that time point;

computing an expected pattern for each invariant of a metric with assumed fault, said pattern indicative of time points at which an invariant will be broken given that its associated metric was affected by a fault at time t;

comparing the expected pattern with the pattern observed over the time window W; and

determining a temporal score based on a match from the prior comparing, said determining comprises, based on observations up to a current time T, selecting an interval of length w, [T−w, T], such that an anomaly at any tε[T−w, T] can cause a broken invariant at T and using an ARX model setting w=arg max(n, m+k).

2. The method of claim 1 , wherein said determining comprises computing an anomaly score assuming that all broken invariants at time t are due to anomalies affecting their corresponding metrics.

3. The method of claim 2 , wherein said determining comprises calculating the anomaly score for t as the sum of the score for each metric with broken invariants at time t.

4. The method of claim 3 , wherein said determining comprises computing the score for a metric based on a match between expected and observed broken invariant pattern, wherein an overall anomaly score for a time t indicates support for an anomaly occurring at this time while the score for a metric denotes how likely it is abnormal.

5. The method of claim 1 , wherein said determining comprises localizing faults in time and ranking abnormal metrics, a time score computation to support that an anomaly occurred at time t, and assuming anomalies happened at time t, assigning a score to a metric m based on the match between an expected temporal pattern of broken invariants and an observed pattern.

6. The method of claim 5 , wherein said localizing faults in time and ranking abnormal risks comprises the following steps:

receiving a set of all invariants I, list of broken invariants Lt at each time point tε[T−w, T], T: current time

for all tε[T−w, T], do anomalyScore[t]=timeScore(t, T, {Lj:j2[t, T]}); and

raise alarms for time points t with high anomaly score; at each of these time points focusing on metrics with high scores for further investigation.

7. The method of claim 5 , wherein said time score computation comprises the following steps:

receiving lists of broken invariants {Lj:j2[t, T]}, set of all invariants I, current time T;

outputting an anomaly score for time t;

for all metric m with broken invariants in Lt, doing score[m]=metricScore(m, {Lj:j 2[t, T]}, I); and

determining an anomaly Score t from Σm score[m].

8. The method of claim 5 , wherein said assigning a score to a metric m includes the following steps:

receiving metric m, set of all invariants I, and list of broken invariants {L j :jε[t, T];

outputting a score for metric m;

initializing a metricScore[m] to 0;

initializing an expectedmetricScore[m] to zero; and

recursively determining metricScore[m] from metricScore[m] divided by expectedMetricScore[m].