About: Sequential Consistency
01

This page probably describes Sequential Consistency not as well as any technical paper, but it is a start.
(See Wikipedia: Sequential Consistency for a brief introduction.)

02 As concluded at About: Messaging [14], every work that is done is based on a message which is handled on an orderly basis.
03 Assuming that based on the same initial state, receiving the same message will produce the same result.
Example: Initial state of a variable i = 0; Received message command: i = i + 1;
04 This assumption even holds when this process is being performed on different machines in parallel.
The step to create a team of sequential consistent processes is now to collect all messages that the system generates and send them to all team members in the same order.
05 As long as the stored state is equal on all members and the identical messages are handled in the identical order the same way, always identical results and identical new messages will be generated - forming a cycle.
06 It is important to note that the members of a consistent team do not do the work at exactly the same time compared to the wall clock. (As literature about distributed systems states, this is not even possible.)
The members do the work the same way in the identical order - Typically within a short period of time as the members should have the same processing capability.
While for the human eye these things happen 'at the same time', they actually don't.
07 The work of collecting messages and distributing them in the same order is done according to a commit protocol, where all participating members of the commit process have to agree on the action.
Such a commit protocol is controlled by one 'special' member, called Coordinator.
08 The commit protocol being used in Semys is the Three Phase Commit Protocol (3PC).
The difference to the 2PC is that the loss of the coordinator itself during a commit can be recovered in all cases.
09 In Semys, members within a group can be divided into any number of subgroups. Each subgroup is a sequential consistent team of members and these subgroups can exchange messages as well.
The Semys architecture specifies that the Center Module creates a group with each registering module where the Center is one subgroup and the module another.
10 While the group communication in the Semys Library allows every combination of members to transport messages to any other combination of members, only a certain set of combinations is commonly used:
  • Local-To-LocalSubgroup: This brings external events into a sequential consistent context
  • LocalSubgroup-To-LocalSubgroup: Standard way of progress in the subgroup
  • Subgroup-To-Other(Subgroup): Typically a message exchange between two subgroups, but may be used for broadcasts as well
11 The rule about identical messages imposes that no local (non-consistent) data may influence the generation of consistent messages. Since the commit protocol matches them according to a hash value (generated from the serialized binary stream), they may not contain different values. While this is a basic rule, it may be bent to enable a further functionality. Local data can be a hostname, current (local) time, result of a call to rand() ...
12 Because messages are matched according to a hash value (called DataKey), the moment after they are registered to be committed, the content is not evaluated anymore - until one consistent instance has been sent from the Coordinator to the group members.
13 The Semys Library allows to pre-specify a DataKey for a data stream that needs to be made consistent. This way a message can be created and filled with consistent data after which a hash will be generated. Then the remaining members of the message are set to local data (for example: a random integer value).
The complete serialized message then is committed with the previsouly generated key and will be matched with the similar messages.
14 The Coordinator chooses one instance of these data streams as the 'master' stream (the first one to arrive) and distributes it to all participants.
After the binary stream has been committed, all destination members will decode one identical message object with previously local data made consistent.
15 Instead of using several Local-To-LocalSubgroup transmissions and agreement handling about any random data, using a predefined DataKey value any random data can be made consistent within a single step - Only requiring that the generation of such a value is clear to the sender beforehand.

Goto: Main Page; This page is part of the Semys software documentation. See About: Documentation for details.