Consistency maintenance

from Wikipedia, the free encyclopedia

The maintaining consistency ( Engl. Consistency control ) is used in the computer science of conservation of consistency in the execution of operations in distributed systems . Maintaining consistency is part of synchronization ; in the Computer Supported Cooperative Work department , it is supplemented by a late join .

The problem

Two subsystems A and B of a distributed system have identical initial states, ie their states are consistent. Now A changes a date x of its state - this is called an operation - and sends the change to B. Almost simultaneously, B also changes the date x of its state and sends a message to A. Since the two changes affect the same date x - one says, they are conflicting - A and B end up having different states after receiving each other's messages. An example:

Hans and Peter play a strategy game over the internet (distributed system) . The game pieces face each other and everyone sees the other player on his screen (consistent initial state) . Now Hans shoots Peter (Operation 1) while at the same time Peter evades (Operation 2) . Hans sees Peter's character collapse on his screen, because due to the network delay, the message about Peter's escape arrives at Hans only a fraction of a second after the shot has hit. On Peter's screen, however, his character is still awake, because due to the network delay, Hans' shot reaches Peter only a fraction of a second after his successful evasive maneuver. With Hans, operation 1 and then operation 2 were carried out, while with Peter the order of execution was exactly the opposite. Due to two simultaneous operations, the state of the distributed system has become inconsistent .

The example shows that both the order in which operations are carried out and when an operation is carried out is critical.

Formalization

Not only when it was created , but also when it is performed is important to an operation . An operation is called dependent on another operation if, from a logical point of view, it has to be carried out after this one. Operations that are not interdependent are concurrent . With these terms, the following criteria can be defined, the fulfillment of which contributes to maintaining consistency:

  • Causality : If a dependent operation is carried out on all instances of the distributed system after the operation on which it depends, one speaks of causality. Causality alone does not guarantee maintenance of consistency, because nothing is said about concurrent operations.
  • Convergence : If all instances of the distributed system carry out the same set of operations and in the end they all have the same state, one speaks of convergence. Convergence is a stronger criterion than causality, but only guarantees that the final state of the instances is the same; Intermediate states assumed temporarily can differ from one another.
  • Correctness : Assume there is a “perfect entity” within the distributed system that performs all operations at the time they are created. If, after performing a set of operations, all instances have the same final state as this perfect instance, one speaks of correctness. Operations that are generated at the same time are arranged one after the other with the help of a "tie-break" criterion. Correctness is the strongest criterion; at the same time it also fulfills the criterion of convergence.

realization

State vectors are used to comply with the criteria for maintaining consistency . When an operation is created, it is assigned a state vector. This contains a sequence number for each instance . The sequence number of an instance indicates which operations this instance has already carried out up to this point in time. The state vector of an operation therefore indicates the states of all instances at the time when the operation was created. Together with the operation, its state vector is now also sent. In addition to the operations, each instance also carries a state vector with it.

The receiver can check the causality criterion in a simple manner by comparing the received state vector with its own state vector. If the sequence number of the instance that generated the operation is exactly 1 greater than the sequence number of this instance in its own vector and all other sequence numbers of the state vector of the operation are less than or equal to the corresponding sequence numbers in its own vector, the operation can be causally executed , ie the causality is preserved in its execution.

The correctness can also be checked with the aid of the state vectors. For this purpose, a relation smaller than is introduced, which compares the sum of all sequence numbers of two state vectors with one another. If the sum of one operation is smaller than that of another, the operation is smaller than the other. If the sum is the same, a tie-break criterion is again used to artificially differentiate the operations from one another; it could e.g. B. Identification numbers of the entities involved are compared. The less than relation automatically also includes the causal dependency; if one operation is smaller than another, the latter also depends on the former.

The less than relation arranges a set of operations as they would be performed by a perfect instance. In order to maintain correctness, an instance must therefore carry out all previous operations in such a way that it assumes the final state that it would have if it had carried out all operations in the order of the less than relation.

Extension to continuous operations

The implementation described so far is tailored to discrete applications, i.e. those that do not involve any temporal processes. However, if the processes are continuous , i.e. the time sequence is also important, the following criteria for maintaining consistency are used:

  • Consistency : If all instances of a distributed system have the same final state at one point in time - after they have received all operations whose execution time is earlier than this point in time - one speaks of consistency. Consistency is a weak criterion because it temporarily allows different intermediate states and does not provide any information about the order in which or at what time the operations actually have to be carried out.
  • Correctness : Assume that there is a perfect instance within the distributed system that does all the operations at the time of execution. If at one point in time - after all operations with an earlier execution time have been received - all instances have the same final state as this perfect instance, then one speaks of correctness. Correctness is the strongest criterion; here, too, it simultaneously fulfills the criterion of convergence.

Operations that are generated absolutely simultaneously should not occur with good clocks, but here too they can be arranged in chronological order with the help of a tie-break criterion. Causality plays a clearly subordinate role here and is only used additionally to avoid gross errors (e.g. changing an object before it was created).

Senseless states

However, the formalized procedures for maintaining consistency described so far all fail due to one hurdle: They cannot see the point of operations. Correspondingly, careful compliance with all consistency maintenance criteria still leads to unpleasant effects:

  • An instance can intermittently have a state that is inconsistent; this is called temporary inconsistency . If this temporary inconsistency is noticed by the user, one speaks of artifacts . Artifacts express themselves e.g. B. in "jumping" characters in computer games when operations that arrive too late are added to the course of the game.
  • If an instance has artifacts, the user can make decisions on the basis of the incorrect information that he would otherwise not have made; one speaks here of secondary inconsistencies . You express yourself z. B. in the fact that the player of a computer game would have reacted differently if he had known that his opponent was already in front of him.