Ensuring properly ordered events in a distributed computing environment
Inventors
Assignees
Publication Number
US-12255978-B2
Publication Date
2025-03-18
Expiration Date
2034-08-18
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
A first event occurs at a first computer at a first time, as measured by a local clock. A second event is initiated at a second computer by sending a message that includes the first time. The second event occurs at a second time, as measured by a local clock. Because of clock error, the first time is later than the second time. Based on the first time being later than the second time, an alternate second time, that is based on the first time, is used as the time of the second event. When a third system determines the order of the two events, the first time is obtained from the first computer, and the alternate second time is obtained from the second computer, and the order of the events is determined based on a comparison of the two times.
Core Innovation
The invention addresses the problem of accurately ordering events in a distributed computing environment where different servers have local clocks that may not be perfectly synchronized, leading to clock errors. Specifically, it provides a method and system to ensure that events processed by multiple different servers can be ordered consistently and correctly despite the inherent inaccuracies and errors of local physical clocks.
The solution involves obtaining a hybrid timestamp for each event, where the timestamp comprises a locally determined physical time value and a global logical sequence number. This hybrid timestamp is used to determine the correct order of events by first comparing the physical time values and, if the events are causally related and have identical physical timestamps, then comparing the logical sequence numbers to resolve ordering.
This method enables correct ordering without requiring waiting for the worst-case synchronization error bound between clocks, thereby avoiding performance delays associated with waiting times while maintaining correct causality. The approach also supports point-in-time snapshot queries using the physical time value component of the hybrid timestamp and can be applied in systems such as social media platforms to correctly order user interactions and enforce privacy or visibility rules based on event order.
Claims Coverage
The patent includes three independent claims covering methods, apparatus, and computer-readable media, focusing on obtaining and using hybrid timestamps to determine event order in distributed systems.
Obtaining hybrid timestamps from multiple servers in a distributed computing system
Obtaining hybrid timestamps for multiple events, where each hybrid timestamp includes a locally determined time value and a global logical sequence number.
Determining event order using hybrid timestamp comparison
Determining the order of multiple events by comparing the hybrid timestamps first based on the locally determined time value and then, if events are causally related and physical times are equal, comparing the global logical sequence number.
Processing requests according to determined event order
Processing requests involving multiple events in a distributed system based on the order determined from comparing their hybrid timestamps.
Applying event ordering agnostic to worst-case synchronization error bound
Determining event order without requiring adherence to or waiting for a worst case synchronization error bound on local clock values.
Supporting causally related events via message prompts
Considering events as causally related when prompted via messages transmitted between different servers, and using this for hybrid timestamp comparison.
Implementing within social media platform interactions
Applying the hybrid timestamp ordering method to events relating to interactions between participants of a social media platform.
Performing point-in-time snapshot queries using physical time values
Processing point-in-time snapshot queries based on the physical time component of the hybrid timestamps associated with events.
The independent claims collectively cover a system and method to obtain hybrid timestamps containing physical time and logical sequence components from multiple distributed servers, compare these timestamps to determine correct event order including for causally related events, apply the order without waiting for worst-case synchronization bounds, and use this ordering within distributed applications such as social media platforms, including supporting snapshot queries.
Stated Advantages
Ensures proper ordering of events in distributed systems despite clock inaccuracies by using hybrid timestamps combining physical time and logical sequence numbers.
Enables event order determination without requiring waiting periods to accommodate worst-case clock synchronization errors, avoiding user frustration and system delays.
Supports correct causality tracking and intuitive physical time ordering for events well-separated in time.
Facilitates applications such as social media platforms to enforce privacy controls and access restrictions based on reliably ordered events.
Allows processing of point-in-time snapshot queries using the physical time component, combining the benefits of physical and logical clocks.
Documented Applications
Ordering events within social media platforms to govern interactions between participants, such as friend and unfriend actions and posts.
Supporting privacy enforcement in social media by ensuring events like unfriending and posting are correctly ordered to control message visibility.
Interested in licensing this patent?