Page History

...

In case of consistent cut every node knows which side of cut a local transaction belongs to (BEFORE or AFTER). On the second picture, node Q after event rcv knows whether tx5 was included to cut on node P. Then if it was, node Q includes it, otherwise doesn't include. 

Paper Algorithm

There is a paper [1] that proposes an algorithm for implementing distributed consistent cut. This algorithm works without a coordinator of the procedure, it is suitable for processes with no-FIFO channels between processes.

Algorithm's purpose is identify wrong order of messages by signing the messages with actual color (red or white). Then every node knows which side of the cut this message belongs to. 

Messages:

1. sent - a set of messages that changed state of a sender.
2. received - a set of messages that changed state of receiver.

Algorithm's steps:

1. Initially all process are white, sent and received collections are empty, LocalState is empty.
2. After some time of system work, every node might have:
   1. Optionally empty collections sent and received
   2. Optionally non-empty LocalState <-> sent + received. State match events that changed its state.
3. Random process can start a snapshot (furthermore, multiple process may start it simultaneously):
   1. Node colors itself to red.
   2. It commits a LocalState.
   3. It commits sent and received as collections for every IN and OUT channel. New one created for next LocalState.
   4. It prepares a marker message: it is red, and has a payload of sent. Goal of the marker is to guarantee order of messages (received_ij must be a subset of sent_ji).
4. Mark every ordinal message between distributed processes with the marker message, if no upcoming message to a node, then it just sends the marker as an ordinary message.
5. On receiving the ordinal message a process has to check the marker at first, before applying the message;
6. If receiving color differs from local color, node has to trigger the local snapshot procedure.
7. Handle sent from the received marker:
   
   1. calculates ChannelState for the channel it received a message: sent - received; where sent extracts from the marker, received - calculates locally since local snapshot.
8. On received marker messages from all IN channels, it prepares a snapshot:
   
   1. Local snapshot of node i: N_i = LocalState_i + Σ ChannelState_ij (sent - received)
9. Every such local snapshot is a unit of global snapshot:
   1. Note, that snapshot consist of committed LocalStates and messages between nodes.
   2. committed sent and received collections are cleaned.

Map the algorithm to Ignite

...