Performing efficient insertions in wavefront table based causal graphs
First Claim
Patent Images
1. A method to be performed on a computing device, comprising:
- receiving data associated with a plurality of events; and
determining causality of one of the events by referencing causal chains of predecessor events stored in entries of a wavefront table associated with the one of the events, with each wavefront table having one or more entries identifying one or more predecessor events of an event in terms of one or more causal chain membership and locations within, and each causal chain having an associated count identifying the highest valid table entry for the causal chain.
3 Assignments
0 Petitions
Accused Products
Abstract
A causal relationship between two events occurs when a first event meaningfully precedes a second event and is identified by a causality module. The causality module analyzes multiple events to determine whether the events are causally related. Reductions in both required storage space and search operations are obtained by tracing interrelated causal chains of events. Further improvement is achieved by reducing re-computation of wavefront tables through annotating causality chain with information that facilitates determination of validity of a wavefront table.
-
Citations
20 Claims
-
1. A method to be performed on a computing device, comprising:
-
receiving data associated with a plurality of events; and determining causality of one of the events by referencing causal chains of predecessor events stored in entries of a wavefront table associated with the one of the events, with each wavefront table having one or more entries identifying one or more predecessor events of an event in terms of one or more causal chain membership and locations within, and each causal chain having an associated count identifying the highest valid table entry for the causal chain. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A device comprising:
-
a communication interface to receive data associated with a plurality of events; and a causality module coupled to the communication interface configured to determine causality of one of the events by referencing causal chains of events stored in entries of a wavefront table associated with the one of the events, with each wavefront table having one or more entries identifying one or more predecessor events of an event in terms of one or more causal chain membership and locations within, and each causal chain having an associated count identifying the highest valid table entry for the causal chain. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
16. An article of manufacture comprising:
-
a storage medium; and a plurality of programming instructions stored on the storage medium and configured to program a system to receive data associated with a plurality of events, and determine causality of one of the events by referencing causal chains of predecessor events stored in entries of a wavefront table associated with the one of the events, with each wavefront table having one or more entries identifying one or more predecessor events of an event in terms of one or more causal chain membership and locations within, and each causal chain having an associated count identifying the highest valid table entry for the causal chain. - View Dependent Claims (17, 18, 19, 20)
-
Specification