Implements Lamport, vector, and hybrid logical clocks for timestamp generation, enabling causal event ordering in distributed systems. Supports concurrency, coroutines, and requires tiebreakers for total ordering.
Surfaced from shared tags and platforms — no rankings paid for.
This library contains implementations of different logical clocks for Kotlin Multiplatform:
pro.felixo.logicalclocks.lamport.LamportClockpro.felixo.logicalclocks.vector.VectorClockpro.felixo.logicalclocks.hybrid.HybridClockAll clocks generate timestamps that can be used to causally order events that occur in a distributed system. Refer to the documentation of the individual clocks, as well as to the articles linked above, for details.
Note that in a distributed system, all of these clocks may generate timestamps that compare equal. Therefore, in case consensus on a strict total ordering of events is required, a tiebreaker must be used. Typically, this is done by including the unique ID of the node that generated the event in the comparison, for example like this:
data class Event(
val timestamp: Long,
val nodeId: String
) : Comparable<Event> {
override fun compareTo(other: Event) =
compareBy<Event> { timestamp }
.thenBy { nodeId }
.compare(this, other)
}
The library contains no platform-specific code.
Note that this library is still in its early stages, and the API is subject to change in any 0.x version.
All clocks implement the LogicalClock interface. In order to generate a timestamp for an event that occurred locally,
call the tick method. When receiving an event from another node, call the tock method with the timestamp of the
received event.
Since in a typical application of logical clocks, I/O and concurrency are involved, the clocks are designed to be used in coroutines and are thread-safe.
A Lamport clock is a simple logical clock that can be used to provide a causal ordering of events. Its potential disadvantage is that it may order concurrent events in a way that is undesirable for a given application.
This is a usage example for a Lamport clock that uses Long as its timestamp type and persists updates using a function
setPersistedTime(time: Long): Unit:
import pro.felixo.logicalclocks.lamport.longLamportClock
val initialTime: Long = getPersistedTime() ?: 0L
// Instantiate the clock. This is a shorthand for: val clock = LamportClock(initialTime, Long::inc, ::persistTime)
val clock: LamportClock<Long> = longLamportClock(
initialTime = initialTime,
onNewTime = ::persistTime
)
// Generate a timestamp for an event that occurred locally:
val timestamp: Long = clock.tick()
// Update the clock with the timestamp of an event that was received from another node:
clock.tock(receivedTimestamp)
Vector clocks generate timestamps with precise information about which events were known at the time that an event occurred. Their disadvantage is that they are large and computationally expensive: their size, as well as the computational complexity of comparing two instances, are proportional to the number of nodes in the system.
This is a usage example for a Vector clock that uses String values to identify nodes, and Long as its timestamp
type. It persists updates using a function persistTime(time: VectorTimestamp<String, Long>): Unit:
import pro.felixo.logicalclocks.vector.VectorClock
import pro.felixo.logicalclocks.vector.VectorTimestamp
val localNodeId = "local"
val initialTime: Long = getPersistedTime() ?: VectorTimestamp("local" to 0L)
// Instantiate the clock:
val clock = VectorClock<String, >(
localNodeId = localNodeId,
initialTime = initialTime,
incrementNodeTime = ::inc,
onNewTime = ::persistTime
)
timestamp: VectorTimestamp<String, > = clock.tick()
clock.tock(receivedTimestamp)
A hybrid logical clock (HLC) that combines a physical clock with a logical component.
It is much like a Lamport clock in that can be used to provide a causal ordering of events. Its advantage over a Lamport clock is that it can additionally order concurrent events using physical time. Note that this advantage is however lost in cases where a participant's physical clock is faulty, especially if it returns times significantly into the future.
Note that the physical component of a timestamp generated by this clock does not necessarily correspond to the actual physical time when the timestamp was generated.
This is a usage example for a Hybrid clock where physical time is expressed as an Instant and the logical component
as a Long. It persists updates using a function persistTime(time: HybridTimestamp<Instant, Long>): Unit:
import kotlinx.datetime.Clock
import kotlinx.datetime.Instant
import pro.felixo.logicalclocks.hybrid.HybridClock
import pro.felixo.logicalclocks.hybrid.HybridTimestamp
physicalClock: Clock = Clock.System
defaultLogicalTime: =
initialTime: = getPersistedTime() ?: HybridTimestamp(physicalClock.now(), defaultLogicalTime)
clock = HybridClock<Instant, >(
initialTime = initialTime,
defaultLogical = defaultLogicalTime,
currentPhysical = { physicalClock.now() },
incrementLogical = ::inc,
onNewTime = ::persistTime
)
timestamp: HybridTimestamp<Instant, > = clock.tick()
clock.tock(receivedTimestamp)
All contributions, whether issues raised or pull requests submitted, are appreciated. If you report a bug, please consider including a unit test that demonstrates it, even if you aren't providing a fix.
This project is licensed under the MIT License.
For any questions, issues, or discussions, feel free to: