Linearizability
Encyclopedia
In concurrent programming, an operation (or set of operations) is atomic, linearizable, indivisible or uninterruptible if it appears to the rest of the system to occur instantaneously. Atomicity is a guarantee of isolation
from concurrent processes
. Additionally, atomic operations commonly have a succeed-or-fail definition — they either successfully change the state of the system, or have no visible effect.
Atomicity is commonly enforced by mutual exclusion
, whether at the hardware level building on a cache coherency
protocol, or the software level using semaphores
or locks
. Thus, an atomic operation does not actually occur instantaneously. The benefit comes from the appearance: the system behaves as if each operation occurred instantly, separated by pauses. Because of this, implementation details may be ignored by the user, except insofar as they affect performance. If an operation is not atomic, the user will also need to understand and cope with sporadic extraneous behaviour caused by interactions between concurrent operations, which by its nature is likely to be hard to reproduce and debug
.
and lock-free and wait-free algorithms. The ability to temporarily inhibit interrupt
s, ensuring that the currently running process
cannot be context switch
ed, also suffices on a uniprocessor
. These instructions are used directly by compiler and operating system writers but are also abstracted and exposed as bytecodes and library functions in higher-level languages.
Most processors
include store operations that are not atomic with respect to memory. These include multiple words stores and string operations. Should a high priority interrupt occur when a portion of the store is complete, the operation must be completed when the interrupt level is returned. The routine that processes the interrupt must not access the memory being changed. It is important to take this into account when writing interrupt routines.
When there are multiple instructions which must be completed without interruption, a CPU instruction which temporarily disables interrupts is used. This must be kept to only a few instructions and the interrupts must be enabled to avoid unacceptable response time to interrupts or even losing interrupts. This mechanism is not sufficient in a multi-processor environment since each CPU has its own interrupt flag.
. Strictly independent operations can then be carefully permitted to overlap their critical sections, provided this does not violate linearizability. Such an approach must balance the cost of large numbers of locks
against the benefits of increased parallelism.
Another approach, favoured by researchers (but not yet widely used in the software industry), is to design a linearizable object using the native atomic primitives provided by the hardware. This has the potential to maximise available parallelism and minimise synchronisation costs, but requires mathematical proofs which show that the objects behave correctly.
A promising hybrid of these two is to provide a transactional memory
abstraction. As with critical sections, the user marks sequential code that must be run in isolation from other threads. The implementation then ensures the code executes atomically. This style of abstraction is common when interacting with databases; for instance, when using the Spring Framework, annotating a method with @Transactional will ensure all enclosed database interactions occur in a single database transaction
. Transactional memory goes a step further, ensuring that all memory interactions occur atomically. As with database transactions, issues arise regarding composition of transactions, especially database and in-memory transactions.
A common theme when designing linearizable objects is to provide an all-or-nothing interface: either an operation succeeds completely, or it fails and does nothing. (ACID
databases refer to this principle as atomicity.) If the operation fails (usually due to concurrent operations), the user must retry, usually performing a different operation. For example:
Now, imagine two processes are running incrementing a single, shared memory location:
but before it can write the new value back to the memory location it is suspended, and the second process is allowed to run:
The second process is suspended and the first process allowed to run again:
This is a trivial example. In a real system, the operations can be more complex and the errors introduced extremely subtle. For example, reading a 64-bit
value from memory may actually be implemented as two sequential
reads of two 32-bit
memory locations. If a process has only read the first 32 bits, and before it reads the second 32 bits the value in memory gets changed, it will have neither the original value nor the new value but a mixed-up garbage
value.
Furthermore, the specific order in which the processes run can change the results, making such an error difficult to detect, reproduce and debug.
instruction that reads from a memory location, compares the value with an "expected" one provided by the user, and writes out a "new" value if the two match, returning whether the update succeeded. We can use this to fix the non-atomic counter algorithm as follows:
Since the compare-and-swap occurs (or appears to occur) instantaneously, if another process updates the location while we are in-progress, the compare-and-swap is guaranteed to fail.
, preventing other threads from disrupting it, using a lock
. Once again fixing the non-atomic counter algorithm:
This strategy works with any problem; compared with direct use of atomic operations, it is relatively easy to get right, but it requires great care to not suffer significant overhead. To improve program performance, it may therefore be a good idea to replace simple critical sections with atomic operations for non-blocking synchronization
(as we have just done for the counter with compare-and-swap), instead of the other way around, but unfortunately a significant improvement is not guaranteed and lock-free algorithms can easily become too complicated to be worth the effort.
by Herlihy and Wing in 1987. It encompassed more restrictive definitions of atomic, such as "an atomic operation is one which cannot be (or is not) interrupted by concurrent operations", which are usually vague about when an operation is considered to begin and end.
An atomic object can be understood immediately and completely from its sequential definition, as a set of operations run in parallel will always appear to occur one after the other; no inconsistencies may emerge. Specifically, linearizability guarantees that the invariants
of a system are observed and preserved by all operations: if all operations individually preserve an invariant, the system as a whole will.
. Each invocation of a function will have a subsequent response. This can be used to model any use of an object. Suppose, for example, that two threads, A and B, both attempt to grab a lock, backing off if it's already taken. This would be modeled as both threads invoking the lock operation, then both threads receiving a response, one successful, one not.
| A invokes lock
| B invokes lock
| A gets "failed" response
| B gets "successful" response>
A sequential history is one in which all invocations have immediate responses. A sequential history should be trivial to reason about, as it has no real concurrency; the previous example was not sequential, and thus is hard to reason about. This is where linearizability comes in.
A history is linearizable if:
(Note that the first two bullet points here match serializability
: the operations appear to happen in some order. It is the last point which is unique to linearizability, and is thus the major contribution of Herlihy and Wing.)
Let us look at two ways of reordering the locking example above.
| A invokes lock
| A gets "failed" response
| B invokes lock
| B gets "successful" response>
Reordering B's invocation below A's response yields a sequential history. This is easy to reason about, as all operations now happen in an obvious order. Unfortunately, it doesn't match the sequential definition of the object: A should have successfully obtained the lock, and B should have subsequently aborted.
| B invokes lock
| B gets "successful" response
| A invokes lock
| A gets "failed" response>
This is another correct sequential history. It is also a linearization! Note that the definition of linearizability only precludes responses that precede invocations from being reordered; since the original history had no responses before invocations, we can reorder it as we wish. Hence the original history is indeed linearizable.
An object (as opposed to a history) is linearizable if all valid histories of its use can be linearized. Note that this is a much harder assertion to prove.
| A invokes lock
| A successfully locks
| B invokes unlock
| B successfully unlocks
| A invokes unlock
| A successfully unlocks
|}>
This history is not valid because there is a point at which both A and B hold the lock; moreover, it cannot be reordered to a valid sequential history without violating the ordering rule. Therefore, it is not linearizable. However, under serializability, B's unlock operation may be moved to before A's original lock, which is a valid history (assuming the object begins the history in a locked state):
| B invokes unlock
| B successfully unlocks
| A invokes lock
| A successfully locks
| A invokes unlock
| A successfully unlocks
|}>
While weird, this reordering is sensible provided there is no alternative means of communicating between A and B. Linearizability is better when considering individual objects separately, as the reordering restrictions ensure that multiple linearizable objects are, considered as a whole, still linearizable.
This alternative is usually much easier to prove. It is also much easier to reason about as a user, largely due to its intuitiveness. This property of occurring instantaneously, or indivisibly, leads to the use of the term atomic as an alternative to the longer "linearizable".
In the examples above, the linearization point of the counter built on CAS is the linearization point of the first (and only) successful CAS update. The counter built using locking can be considered to linearize at any moment while the locks are held, since any potentially conflicting operations are excluded from running during that period.
is the most stringent consistency model
. It says that a read operation has to return the result of the latest write operation which occurred on that data item
.
Isolation (computer science)
In database systems, isolation is a property that defines how/when the changes made by one operation become visible to other concurrent operations. Isolation is one of the ACID properties.-Isolation levels:...
from concurrent processes
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
. Additionally, atomic operations commonly have a succeed-or-fail definition — they either successfully change the state of the system, or have no visible effect.
Atomicity is commonly enforced by mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
, whether at the hardware level building on a cache coherency
Cache coherency
In computing, cache coherence refers to the consistency of data stored in local caches of a shared resource.When clients in a system maintain caches of a common memory resource, problems may arise with inconsistent data. This is particularly true of CPUs in a multiprocessing system...
protocol, or the software level using semaphores
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
or locks
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
. Thus, an atomic operation does not actually occur instantaneously. The benefit comes from the appearance: the system behaves as if each operation occurred instantly, separated by pauses. Because of this, implementation details may be ignored by the user, except insofar as they affect performance. If an operation is not atomic, the user will also need to understand and cope with sporadic extraneous behaviour caused by interactions between concurrent operations, which by its nature is likely to be hard to reproduce and debug
Debugging
Debugging is a methodical process of finding and reducing the number of bugs, or defects, in a computer program or a piece of electronic hardware, thus making it behave as expected. Debugging tends to be harder when various subsystems are tightly coupled, as changes in one may cause bugs to emerge...
.
Primitive atomic instructions
Processors have instructions that can be used to implement lockingLock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
and lock-free and wait-free algorithms. The ability to temporarily inhibit interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s, ensuring that the currently running process
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
cannot be context switch
Context switch
A context switch is the computing process of storing and restoring the state of a CPU so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system...
ed, also suffices on a uniprocessor
Uniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
. These instructions are used directly by compiler and operating system writers but are also abstracted and exposed as bytecodes and library functions in higher-level languages.
- Atomic read-write
- Atomic swap as used in some Burroughs mainframes, also called XCHG.
- Test-and-setTest-and-setIn computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
- Fetch-and-addFetch-and-addIn computer science, the fetch-and-add CPU instruction is a special instruction that atomically modifies the contents of a memory location. It is used to implement mutual exclusion and concurrent algorithms in multiprocessor systems, a generalization of semaphores.In uniprocessor systems, it is...
- Compare-and-swapCompare-and-swapIn computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
- Load-Link/Store-ConditionalLoad-Link/Store-ConditionalIn computer science, load-link and store-conditional are a pair of instructions that together implement a lock-free atomic read-modify-write operation....
Most processors
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
include store operations that are not atomic with respect to memory. These include multiple words stores and string operations. Should a high priority interrupt occur when a portion of the store is complete, the operation must be completed when the interrupt level is returned. The routine that processes the interrupt must not access the memory being changed. It is important to take this into account when writing interrupt routines.
When there are multiple instructions which must be completed without interruption, a CPU instruction which temporarily disables interrupts is used. This must be kept to only a few instructions and the interrupts must be enabled to avoid unacceptable response time to interrupts or even losing interrupts. This mechanism is not sufficient in a multi-processor environment since each CPU has its own interrupt flag.
High-level atomic operations
The easiest way to achieve linearizability is running groups of primitive operations in a critical sectionCritical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
. Strictly independent operations can then be carefully permitted to overlap their critical sections, provided this does not violate linearizability. Such an approach must balance the cost of large numbers of locks
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
against the benefits of increased parallelism.
Another approach, favoured by researchers (but not yet widely used in the software industry), is to design a linearizable object using the native atomic primitives provided by the hardware. This has the potential to maximise available parallelism and minimise synchronisation costs, but requires mathematical proofs which show that the objects behave correctly.
A promising hybrid of these two is to provide a transactional memory
Transactional memory
Transactional memory attempts to simplify parallel programming by allowing a group of load and store instructions to execute in an atomic way. It is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing.-Hardware vs...
abstraction. As with critical sections, the user marks sequential code that must be run in isolation from other threads. The implementation then ensures the code executes atomically. This style of abstraction is common when interacting with databases; for instance, when using the Spring Framework, annotating a method with @Transactional will ensure all enclosed database interactions occur in a single database transaction
Database transaction
A transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
. Transactional memory goes a step further, ensuring that all memory interactions occur atomically. As with database transactions, issues arise regarding composition of transactions, especially database and in-memory transactions.
A common theme when designing linearizable objects is to provide an all-or-nothing interface: either an operation succeeds completely, or it fails and does nothing. (ACID
ACID
In computer science, ACID is a set of properties that guarantee database transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction...
databases refer to this principle as atomicity.) If the operation fails (usually due to concurrent operations), the user must retry, usually performing a different operation. For example:
- Compare-and-swapCompare-and-swapIn computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
writes a new value into a location only if the latter's contents matches a supplied old value. This is commonly used in a read-modify-CAS sequence: the user reads the location, computes a new value to write, and writes it with a CAS; if the value changes concurrently, the CAS will fail and the user tries again. - Load-Link/Store-ConditionalLoad-Link/Store-ConditionalIn computer science, load-link and store-conditional are a pair of instructions that together implement a lock-free atomic read-modify-write operation....
encodes this pattern more directly: the user reads the location with load-link, computes a new value to write, and writes it with store-conditional; if the value has changed concurrently, the SC will fail and the user tries again. - In a database transactionDatabase transactionA transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
, if the transaction cannot be completed due to a concurrent operation (e.g. in a deadlockDeadlockA deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
), the transaction will be aborted and the user must try again.
Non-atomic
The naive, non-atomic implementation:- reads the value in the memory location;
- adds one to the value;
- writes the new value back into the memory location.
Now, imagine two processes are running incrementing a single, shared memory location:
- the first process reads the value in memory location;
- the first process adds one to the value;
but before it can write the new value back to the memory location it is suspended, and the second process is allowed to run:
- the second process reads the value in memory location, the same value that the first process read;
- the second process adds two to the value;
- the second process writes the new value into the memory location.
The second process is suspended and the first process allowed to run again:
- the first process writes a now-wrong value into the memory location, unaware that the other process has already updated the value in the memory location.
This is a trivial example. In a real system, the operations can be more complex and the errors introduced extremely subtle. For example, reading a 64-bit
64-bit
64-bit is a word size that defines certain classes of computer architecture, buses, memory and CPUs, and by extension the software that runs on them. 64-bit CPUs have existed in supercomputers since the 1970s and in RISC-based workstations and servers since the early 1990s...
value from memory may actually be implemented as two sequential
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
reads of two 32-bit
32-bit
The range of integer values that can be stored in 32 bits is 0 through 4,294,967,295. Hence, a processor with 32-bit memory addresses can directly access 4 GB of byte-addressable memory....
memory locations. If a process has only read the first 32 bits, and before it reads the second 32 bits the value in memory gets changed, it will have neither the original value nor the new value but a mixed-up garbage
Garbage (computer science)
Garbage, in the context of computer science, refers to objects, data, or other regions of the memory of a computer system , which will not be used in any future computation by the system, or by a program running on it...
value.
Furthermore, the specific order in which the processes run can change the results, making such an error difficult to detect, reproduce and debug.
Compare-and-swap
Most systems provide an atomic compare-and-swapCompare-and-swap
In computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
instruction that reads from a memory location, compares the value with an "expected" one provided by the user, and writes out a "new" value if the two match, returning whether the update succeeded. We can use this to fix the non-atomic counter algorithm as follows:
-
- read the value in the memory location;
- add one to the value
- use compare-and-swap to write the incremented value back
- retry if the value read in by the compare-and-swap did not match the value we originally read
Since the compare-and-swap occurs (or appears to occur) instantaneously, if another process updates the location while we are in-progress, the compare-and-swap is guaranteed to fail.
Locking
Another approach is to turn the naive algorithm into a critical sectionCritical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
, preventing other threads from disrupting it, using a lock
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
. Once again fixing the non-atomic counter algorithm:
-
- take a lock, excluding other threads from running the critical section (steps 2-4) at the same time
- read the value in the memory location
- add one to the value
- write the incremented value back to the memory location
- release the lock
This strategy works with any problem; compared with direct use of atomic operations, it is relatively easy to get right, but it requires great care to not suffer significant overhead. To improve program performance, it may therefore be a good idea to replace simple critical sections with atomic operations for non-blocking synchronization
Non-blocking synchronization
In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion...
(as we have just done for the counter with compare-and-swap), instead of the other way around, but unfortunately a significant improvement is not guaranteed and lock-free algorithms can easily become too complicated to be worth the effort.
History of linearizability
Linearizability was first introduced as a consistency modelConsistency model
In computer science, consistency models are used in distributed systems like distributed shared memory systems or distributed data stores . The system supports a given model, if operations on memory follow specific rules...
by Herlihy and Wing in 1987. It encompassed more restrictive definitions of atomic, such as "an atomic operation is one which cannot be (or is not) interrupted by concurrent operations", which are usually vague about when an operation is considered to begin and end.
An atomic object can be understood immediately and completely from its sequential definition, as a set of operations run in parallel will always appear to occur one after the other; no inconsistencies may emerge. Specifically, linearizability guarantees that the invariants
Invariant (computer science)
In computer science, a predicate is called an invariant to a sequence of operations provided that: if the predicate is true before starting the sequence, then it is true at the end of the sequence.-Use:...
of a system are observed and preserved by all operations: if all operations individually preserve an invariant, the system as a whole will.
Definition of linearizability
A history is a sequence of invocations and responses made of an object by a set of threadsThread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
. Each invocation of a function will have a subsequent response. This can be used to model any use of an object. Suppose, for example, that two threads, A and B, both attempt to grab a lock, backing off if it's already taken. This would be modeled as both threads invoking the lock operation, then both threads receiving a response, one successful, one not.
| B invokes lock
| A gets "failed" response
| B gets "successful" response>
A sequential history is one in which all invocations have immediate responses. A sequential history should be trivial to reason about, as it has no real concurrency; the previous example was not sequential, and thus is hard to reason about. This is where linearizability comes in.
A history is linearizable if:
- its invocations and responses can be reordered to yield a sequential history
- that sequential history is correct according to the sequential definition of the object
- if a response preceded an invocation in the original history, it must still precede it in the sequential reordering
(Note that the first two bullet points here match serializability
Serializability
In concurrency control of databases, transaction processing , and various transactional applications , both centralized and distributed, a transaction schedule is serializable, has the serializability property, if its outcome In concurrency control of databases, transaction processing (transaction...
: the operations appear to happen in some order. It is the last point which is unique to linearizability, and is thus the major contribution of Herlihy and Wing.)
Let us look at two ways of reordering the locking example above.
| A gets "failed" response
| B invokes lock
| B gets "successful" response>
Reordering B's invocation below A's response yields a sequential history. This is easy to reason about, as all operations now happen in an obvious order. Unfortunately, it doesn't match the sequential definition of the object: A should have successfully obtained the lock, and B should have subsequently aborted.
| B gets "successful" response
| A invokes lock
| A gets "failed" response>
This is another correct sequential history. It is also a linearization! Note that the definition of linearizability only precludes responses that precede invocations from being reordered; since the original history had no responses before invocations, we can reorder it as we wish. Hence the original history is indeed linearizable.
An object (as opposed to a history) is linearizable if all valid histories of its use can be linearized. Note that this is a much harder assertion to prove.
Linearizability versus serializability
Consider the following history, again of two objects interacting with a lock:| A successfully locks
| B invokes unlock
| B successfully unlocks
| A invokes unlock
| A successfully unlocks
|}>
This history is not valid because there is a point at which both A and B hold the lock; moreover, it cannot be reordered to a valid sequential history without violating the ordering rule. Therefore, it is not linearizable. However, under serializability, B's unlock operation may be moved to before A's original lock, which is a valid history (assuming the object begins the history in a locked state):
| B successfully unlocks
| A invokes lock
| A successfully locks
| A invokes unlock
| A successfully unlocks
|}>
While weird, this reordering is sensible provided there is no alternative means of communicating between A and B. Linearizability is better when considering individual objects separately, as the reordering restrictions ensure that multiple linearizable objects are, considered as a whole, still linearizable.
Linearization points
This definition of linearizability is equivalent to the following:- All function calls have a linearization point at some instant between their invocation and their response
- All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition
This alternative is usually much easier to prove. It is also much easier to reason about as a user, largely due to its intuitiveness. This property of occurring instantaneously, or indivisibly, leads to the use of the term atomic as an alternative to the longer "linearizable".
In the examples above, the linearization point of the counter built on CAS is the linearization point of the first (and only) successful CAS update. The counter built using locking can be considered to linearize at any moment while the locks are held, since any potentially conflicting operations are excluded from running during that period.
Strict consistency
Strict consistency in computer scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
is the most stringent consistency model
Consistency model
In computer science, consistency models are used in distributed systems like distributed shared memory systems or distributed data stores . The system supports a given model, if operations on memory follow specific rules...
. It says that a read operation has to return the result of the latest write operation which occurred on that data item
Data item
A data item describes an atomic state of a particular object concerning a specific property at a certain time point. A collection of data items for the same object at the same time forms an object instance . Any type of complex information can be broken down to elementary data items...
.