Liveness

In concurrent computing, liveness refers to a set of properties of concurrent systems, that require a system to make progress despite the fact that its concurrently executing components ("processes") may have to "take turns" in critical sections, parts of the program that cannot be simultaneously run by multiple processes.[1] Liveness guarantees are important properties in operating systems and distributed systems.[2]

A liveness property cannot be violated in a finite execution of a distributed system because the "good" event might only theoretically occur at some time after execution ends. Eventual consistency is an example of a liveness property.[3] All properties can be expressed as the intersection of safety and liveness properties[4] and most non-trivial properties are a mix of the two.

Forms of liveness

Several forms of liveness are recognized. The following ones are defined in terms of a multi-process system that has a critical section, protected by some mutual exclusion (mutex) device. All processes are assumed to correctly use the mutex; progress is defined as finishing execution of the critical section.

See also

References

  1. Lamport, L. (1977). "Proving the Correctness of Multiprocess Programs". IEEE Transactions on Software Engineering (2): 125–143. doi:10.1109/TSE.1977.229904.
  2. Luís Rodrigues, Christian Cachin; Rachid Guerraoui (2010). Introduction to reliable and secure distributed programming (2. ed.). Berlin: Springer Berlin. pp. 22–24. ISBN 978-3-642-15259-7.
  3. Bailis, P.; Ghodsi, A. (2013). "Eventual Consistency Today: Limitations, Extensions, and Beyond". Queue 11 (3): 20. doi:10.1145/2460276.2462076.
  4. Alpern, B.; Schneider, F. B. (1987). "Recognizing safety and liveness". Distributed Computing 2 (3): 117. doi:10.1007/BF01782772.
  5. 1 2 3 Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. pp. 10–11. ISBN 3642320279.

External links


This article is issued from Wikipedia - version of the Wednesday, September 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.