kernel.core.causal-dag
Causal Directed Acyclic Graph, CDAG for short. The CDAG captures compound operations’ dependencies.
Nodes in the CDAG are operations. Two operations A and B are connected if and only if (preceding? A B) with kernel.core.compound-operation/preceding?.
The CDAG is required to obtain all causally preceding operations (CP) efficiently for a given operation. Further, it is used to obtain all causally immediate preceding operations (CIP).
The CP can easily be computed by determining causally-preceding relationships. The CIP corresponds to a transitive reduction of the CDAG and can thus be obtained from the CP by removing all transitive edges. (See minimum equivalent graph / maximal elements of CP.)
The CP is unique across all sites as all operations causally preceding an operation always arrive before said operation (guaranteed by TCP). For finite DAGs as the CDAG the transitive reduction is unique, therefore the CIP is also unique across all sites.
The CDAG is implemented by mapping compound operations to their respective CPs and CIPs, allowing O(1) access.
If no garbage collection is performed, the CDAG might grow quadratically with time.
_remove
(_remove CDAG CO-ID)Removes an operation from the CDAG in O(n). Removes the operation’s CP and CIP. Also removes the operation from all other operations’ CPs and CIPs.
get-CIP
(get-CIP CDAG CO-ID)Returns a set of all causally immediately preceding operations for a compound operation in O(1). This excludes transitive edges.
get-CO-IDs
(get-CO-IDs CDAG)Returns a sequence of all compound operation identifiers contained in the CDAG.
get-CP
(get-CP CDAG CO-ID)Returns a set of all causally preceding operations for a compound operation in O(1). This includes transitive edges.
insert
(insert CDAG HB CO)Inserts a newly received operation into the CDAG. Calculates the CP by scanning all previously received operations in O(n). Calculates the CIP by filtering the CP and removing any operations that are succeeded by any other operation in the CP, yielding the maximum elements of the CP or the transitive reduction.
remove-all-occurrences
(remove-all-occurrences m val)Removes all occurrences of a value from all sets that m maps to.