3.1.1 Abstract Data Model

This section describes a conceptual model of possible data organization that an implementation maintains to participate in this protocol. The described organization is provided to facilitate the explanation of how the protocol behaves. This document does not mandate that implementations adhere to this model as long as their external behavior is consistent with that described in this document.

Delta Log: The delta log contains the history of all deltas that have been executed. The deltas should be organized sequentially by order of execution.

Dependency Graph: The set of dependencies on the deltas is representable as a directed acyclic graph. The deltas are vertices. The edges are the immediate dependencies of a delta. Edges are added so that there is at most one path between any two vertices. A delta A1 depends on a different delta B1 if and only if there is a path from A1 to B1 in the dependency graph. This is shown in the following diagram.

Figure 1: Sample dependency graph

The preceding graph results from the following steps:

1. A creates A1.

2. B, C receive A1.

3. A creates A2.

4. C receives A2.

5. B creates B1.

6. A,C receive B1.

7. C creates C1.

8. A receives C1.

9. B creates B2.

10. A creates A3.

Endpoint Space State: The last known space state for each endpoint. The following information is kept for each endpoint:

• Rank: The highest rank of the deltas executed on the endpoint.

• Min Dependency Group: The minimum dependency group declared by the endpoint.

• Purge Group: The group number that the endpoint is willing to purge.

• Dependencies: The sources of the dependency graph on the endpoint.