Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12468682-B2
Publication Date
2025-11-11
Expiration Date
Abstract
A device implementing a system for obtaining a consistent state of data based on data updates made on different devices includes a processor configured to generate, for a first data update, a first data model including first data nodes, each including a first identifier and a first data value corresponding to one of first data objects. The processor is configured to receive from a second device, for a second data update to the data, the second update being independent of the first update, a second data model including second data nodes, each including a second identifier and a second data value corresponding to one of second data objects. A consistent data model is obtained by merging the first and second data values with the same identifier, and then merging the first and second data models, and generating a final update of the data based on the consistent data model.
Core Innovation
The invention generates, at a first device with respect to a first update to data provided to an application at the first device, a first data model including a first plurality of data nodes. Each data node includes a first identifier and a first data value corresponding to a data object included in the first update, and each data node is implemented as a conflict-free replicated data type (CRDT) and references another data node. The invention also generates, at a second device with respect to a second update to the data provided to the application at the second device, a second data model including a second plurality of data nodes. Each data node includes a second identifier and a second data value corresponding to a data object included in the second update, and each data node is implemented as a respective CRDT and references another data node.
The invention generates a consistent data model based on the first and second data models by merging the first and second data values for the same data object for which the first identifier is equal to the second identifier. The consistent data model includes data nodes having the merged first and second data values, and data nodes unique to the first or second data model. The invention further generates a final update of the data based on the consistent data model. This framework synchronizes independent updates to application data across devices by producing a consistent model and using it to generate the final update.
The invention addresses an inconsistency problem arising from non-guaranteed associativity of merge behavior when a target data object is deleted and then reinsertion occurs. In such cases, the invention detects the reinsertion and identifies the target data node as an inconsistent data node. The inconsistent designation represents uncertainty over whether the reinserted target data node should have the current data value or the new data value in the consistent data model. In some embodiments, the invention resolves the uncertainty by using globally-synchronized timestamps associated with the value update and the duplication update.
The invention represents the application data as a rooted directed graph in some embodiments, where both the first data model and the second data model include a root node identifying the application that references the data nodes directly or indirectly. In further embodiments, the data nodes are interconnected by edges in the graph. The invention can also constrain the semantics and identity mapping by associating the data objects with electronically generated application content types, and by enforcing uniqueness rules among first and second identifiers.
Claims Coverage
The independent claims cover a method, a device, and a computer program product that generate CRDT-based data models for independent updates on separate devices, merge matching data objects or identifiers into a consistent data model, and generate a final update. The claim set includes at least four core inventive features in the independent claim text: CRDT-based node models with identifiers and references, cross-device merging of values for matching identifiers, forming a consistent model that includes both merged and unique nodes, and generating a final update; additional refinement embodiments add reinsertion inconsistency handling, uncertainty resolution via globally-synchronized timestamps, and rooted graph structure.
CRDT-based data model nodes with identifiers and references
generating at a first device and a second device respective data models including pluralities of data nodes, wherein each data node includes an identifier and a data value corresponding to a data object, wherein each data node is implemented as a respective CRDT and one or more data nodes references another data node
Consistent data model by merging values for matching identifiers and retaining unique nodes
generating a consistent data model based on the first and second data models by merging the first and second data values for a same data object for which the first identifier is equal to the second identifier, and merging the first and second data models such that the consistent data model includes data nodes having the merged first and second data values, and data nodes which are unique to the first or second data model
Final update generation based on consistent data model
generating a final update of the data based on the consistent data model
Inconsistent data node handling for deletion followed by reinsertion
receiving deletion and duplication updates for a target data node, detecting reinsertion, and identifying the target data node as an inconsistent data node to indicate uncertainty over whether the reinserted target data node should have the current data value or the new data value
Uncertainty resolution using globally-synchronized timestamps
resolving the uncertainty for a value update and a duplication update using globally-synchronized timestamps
Root node application graph structure and edge interconnection
generating first and second data models including a root node that identifies the application and references a plurality of data nodes, and interconnecting the data nodes by edges in the graph
Across the independent claim set, the inventive subject matter is centered on generating CRDT-based data-node models for independent device updates, merging node values for matching identifiers while retaining nodes unique to each update, and generating a final update from the consistent model. Dependent refinements further specify reinsertion-related inconsistency detection and optional uncertainty resolution using globally-synchronized timestamps, and in some embodiments define a rooted graph structure with edges and an application-identifying root node.
Stated Advantages
Conflict-free replicated data type (CRDT) based merging to generate a consistent data model and a final update from independent updates across devices.
Retention of data nodes unique to one device while merging data values for matching identifiers into the consistent data model.
Handling of deletion followed by reinsertion by identifying target data nodes as inconsistent to represent uncertainty about the final data value.
Resolution of uncertainty using globally-synchronized timestamps for a value update and a duplication update.
Support for an application-identifying rooted graph structure for representing the data model, including direct or indirect referencing of data nodes by the root node.
Documented Applications
Collaborative or concurrent editing of application data across devices, including scenarios described with device/UI updates (e.g., offline support and undo/redo are mentioned in the provided summary of the document content).
Interested in licensing this patent?