ordered message delivery
Foundational classes for establishing ordered delivery of messages to concurrent processes, with Vector Clock and Tree Clock implementations and process examples.
Feedback and contributions welcome!
The main building block is a MessageService, which is intended to be interposed between an application process (such as an Actor or Verticle) and the message transport (such as a realtime channel, websocket, or queue consumer).
The MessageService maintains an internal clock state to determine the correct delivery order for incoming messages. It relies on the process to call its send and receive methods when sending or receiving a message from the transport; in doing so, the clock is suitably updated, and the message payload can be wrapped up or unwrapped and delivered, respectively.
An example process is provided, as a generic Java class for the update of a CRDT requiring causal delivery, and further subclassed in a very naive fashion to implement an OR-Set (Observed-Removed-Set).
Two MessageService implementations are provided: a Vector Clock service and a Tree Clock service, which is more efficient for dynamic systems.
- Concurrent and Distributed Systems Process groups and message ordering, University of Cambridge Computer Laboratory Course material 2009–10, https://www.cl.cam.ac.uk/teaching/0910/ConcDistS/10b-ProcGp-order.pdf
- Paulo Sergio Almeida, Carlos Baquero, Victor Fonte, Interval Tree Clocks, http://gsd.di.uminho.pt/members/cbm/ps/itc2008.pdf
- GitHub, Voldemort is a distributed key-value storage system, https://github.com/voldemort/voldemort/blob/master/src/java/voldemort/versioning/VectorClock.java
- GitHub, A ShiViz-compatible logging library for Java, https://github.com/DistributedClocks/JVector/blob/master/jvec/org/github/com/jvec/vclock/VClock.java
- GitHub, Java implementation of a multicast-chat, https://github.com/matteotiziano/multicast-chat/blob/master/src/model/VectorClock.java
- GitHub, An Implementation of Interval Tree Clock, https://github.com/sinabz/itc4j
- GitHub, A Logical Clock for Static and Dynamic Systems, https://github.com/ricardobcl/Interval-Tree-Clocks