1
$\begingroup$

In the book A Science of Concurrent Programs Leslie Lamport describes alternative way how to look at safety and liveness properties in distributed algorithms.

A.5 Another Way to Look at Safety and Liveness This section provides a different view of safety and liveness based on viewing behavior predicates as sets of behaviors. This view was first recognized by Gordon Plotkin. I find that it helps me understand safety and liveness. To understand it, we first need some more math.

They build a metric space where distance between behaviors is defined as $\delta(x, y) = 1/(1 + commonPrefixLength(x, y))$

Where can I read about this topological/metric space?

I am interested, in particular:

  1. What would be the open sets? All behaviors starting with the finit prefixes?
  2. What would be a closed set? In my understanding, open set will be also closed. Given an open set $U$ of behaviors starting with prefix a,b,c, then any behavior outside of this set, for example, a,b,x,... will belong to another open set, and therefore will not be a limit point of $U$.
  3. What would be a dense set? I think dense set will be a set consisting of all behaviors ending with stuttering steps - infinite tails where state of the system does not change.
$\endgroup$

1 Answer 1

2
$\begingroup$

The standard reference for the topological characterisation is Bowen Alpern and Fred B. Schneider. Defining liveness. Information Processing Letters, 21(4): 181–185, October 1985.

One notable difference to Lamport's characterisation is that Alpern & Schneider don't insist on stuttering closure. If I recall correctly, if one wanted to characerise both versions of safety properties via closures, one would say that a Lamport safety property is a set of behaviours closed under all forms of stuttering (finite, anywhere in a behaviour, and infinite, at the end). In Alpern & Schneider's setting safety properties are those sets of behaviours closed under (a) prefix (similar to closure under infinite stuttering only) and limits (of sequences of behaviours that agree on ever longer prefixes).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.