Editing Linearizability (section)

==== Non-atomic ====
The naive, non-atomic implementation:

'''Increment:'''
# Read the value in the register R
# Add one to the value
# Writes the new value back into register R
'''Read:'''

Read register R

This simple implementation is not linearizable, as is demonstrated by the following example.

Imagine two processes are running accessing the single counter object initialized to have value 0:
# The first process reads the value in the register as 0.
# The first process adds one to the value, the counter's value should be 1, but before it has finished writing the new value back to the register it may become suspended, meanwhile the second process is running:
# The second process reads the value in the register, which is still equal to 0;
# The second process adds one to the value;
# The second process writes the new value into the register, the register now has value 1.
The second process is finished running and the first process continues running from where it left off:
# The first process writes 1 into the register, unaware that the other process has already updated the value in the register to 1.
In the above example, two processes invoked an increment command, however the value of the object only increased from 0 to 1, instead of 2 as it should have. One of the increment operations was lost as a result of the system not being linearizable.

The above example shows the need for carefully thinking through implementations of data structures and how linearizability can have an effect on the correctness of the system.