In other words, a fluent holds at a time instant if and only if it holds initially or some initiating action has occurred, and, in both cases, no terminating action has yet occurred. The following fragment defines a fluent LIGHT which becomes true when the action on occurs and false when the action off or power_cut occurs.

const False = 0
const True  = 1
fluent LIGHT = <{on}, {off, power_cut}> initially False

We can think of the above fluent as capturing the state of a light such that when the light is on, the fluent LIGHT is true and when the light is off, the fluent LIGHT is false. We can define indexed families of fluents in the same way that we define indexed families of processes:

fluent LIGHT[i:1..2] = <{on[i]}, {off[i], power_cut}>

This is equivalent to defining two fluents:

fluent LIGHT_1 = <{on[1]}, {off[1], power_cut}>
fluent LIGHT_2 = <{on[2]}, {off[2], power_cut}<

We can combine fluents with the normal logical operators. If we wished to characterize the state in which two lights are on, this would be the expression LIGHT[1] && LIGHT[2]. The state in which either light is on would be LIGHT[1] || LIGHT[2]. This latter would also be true if both lights were on. Fluent expressions can be formed using the following logical operators:

For example, given the fluents:

fluent POWER  = <power_on, power_off>
fluent LIGHT  = <on, off>

the expression LIGHT->POWER states our expectation that, for the light to be on, the power must also be on. We do not expect that if the power is on the light need necessarily be on as well.

If we wish to express the proposition that all lights are on, we can use the expression:

forall[i:1..2] LIGHT[i]

This is exactly the same as LIGHT[1] && LIGHT[2]. In a similar way, if we wish to express the proposition that at least one light is on, we can state:

exists[i:1..2] LIGHT[i]

This is exactly the same as LIGHT[1] || LIGHT[2].

An expression that combines an action fluent and an explicitly defined fluent is (getkey && LIGHT[1]) which is true when the getkey action occurs when the LIGHT fluent is true – i.e., the light has previously been turned on.

To illustrate the expression of safety properties using fluents, we return to the mutual exclusion example of section 7.1.2.

const N = 2

LOOP = (mutex.down -> enter -> exit -> mutex.up -> LOOP).

||SEMADEMO = (p[1..N]:LOOP
          || {p[1..N]}::mutex:SEMAPHORE(1)).

The abstract states of interest here are when each LOOP process enters its critical section. We express these states with fluents:

fluent CRITICAL[i:1..N] = <p[i].enter, p[i].exit>

We can express the situation in which two processes are in their critical sections at thesametimeas CRITICAL[1] && CRITICAL[2]. This situation must be avoided at all costs since it violates mutual exclusion. How do we assert that this situation does not occur at any point in the execution of the SEMADEMO system?

Given this operator, we can now express the property that at all times in any execution of the system, CRITICAL[1] && CRITICAL[2] must not occur. This is:

assert MUTEX = []!(CRITICAL[1] && CRITICAL[2])

This property is checked by compiling it into a safety property process. As described in Chapter 7, the check is then performed by composing this property with the system and performing an exhaustive search for the ERROR state. The property process compiled from MUTEX above is depicted in Figure 14.1.

Figure 14.1. MUTEX property process.

The MUTEX property is not violated with the semaphore initialized to one; however if we initialize the semaphore to two (i.e. SEMAPHORE(2)) then a check of the MUTEX property against the SEMADEMO system produces the following trace:

Trace to property violation in MUTEX:
           p.1.mutex.down
           p.1.enter           CRITICAL.1
           p.2.mutex.down      CRITICAL.1
           p.2.enter           CRITICAL.1 && CRITICAL.2

The LTSA annotates the trace with the names of the fluents that are true when the action on the left occurs. So, when the action p.2.enter occurs, both of the CRITICAL fluents are true, violating mutual exclusion. The general expression of the mutual exclusion property for N processes is:

assert MUTEX_N = []!(exists [i:1..N-1]
                 (CRITICAL[i] && CRITICAL[i+1..N]))

This asserts that it is always the case that no pair of processes exist with CRITICAL true. CRITICAL[i+1..N] is a short form for the disjunction exists [j:i+1..N] CRITICAL[j].

const N = 3    // number of each type of car
range ID= 1..N // car identities

fluent RED[i:ID]  = <red[i].enter, red[i].exit>
fluent BLUE[i:ID] = <blue[i].enter, blue[i].exit>

assert ONEWAY = []!(exists[i:ID] RED[i]
                && exists[j:ID] BLUE[j])

Trace to property violation in ONEWAY:
           red.1.enter         RED.1
           blue.1.enter        RED.1 && BLUE.1

assert ONEWAY = []!(RED[ID] && BLUE[ID])

A safety property asserts that nothing bad ever happens whereas a liveness property asserts that something good eventually happens. Linear temporal logic provides the eventually operator which allows us to directly express the progress properties we introduced in Chapter 7.

We can now assert for the single-lane bridge example that eventually the first red car must enter the bridge:

assert FIRSTRED = <>red[1].enter

Figure 14.2. Büchi automaton for FIRSTRED.

This is compiled into the transition system shown in Figure 14.2. This is a special form of transition system known as a Büchi automaton after its originator. A Büchi automaton recognizes an infinite trace if that trace passes through an acceptance state infinitely often. The example of Figure 14.2 has a single acceptance state marked by two concentric rings. It should be clear that any trace containing the action red[1].enter is not accepted by this automaton since the action will move the automaton irretrievably out of the initial acceptance state.

In fact, the Büchi automaton of Figure 14.2 accepts the set of infinite traces represented by the negation of the FIRSTRED property – that is, !<>red[1].enter. To check whether an assertion holds, the LTSA constructs a Büchi automaton for the negation of the assertion and then checks whether there are any infinite traces that are accepted when the automaton is combined with the model. This check can be performed efficiently since it is a search for acceptance states in strongly connected components. If none are found then there is no trace that satisfies the negation of the property and consequently the property holds. We discussed strongly connected components and their relationship to infinite executions in Chapter 7. In checking liveness properties, we make exactly the same fair choice assumption as was made in Chapter 7. The property is satisfied for the basic bridge model but not for the congested model defined by:

||CongestedBridge
           = SingleLaneBridge > {red[ID].exit,blue[ID].exit}.

The following property violation is reported for a system with two red cars and two blue cars:

Violation of LTL property: @FIRSTRED
     Trace to terminal set of states:
           blue.1.enter
     Cycle in terminal set:
           blue.2.enter
           blue.1.exit
           blue.1.enter
           blue.2.exit
     LTL Property Check in: 10ms

Figure 14.3. CongestedBridge showing acceptance states.

The model, combined with the FIRSTRED property, is shown in Figure 14.3. The connected component (states 1,2,3,4) containing acceptance states can clearly be seen.

The property FIRSTRED is satisfied if the first red car enters the bridge a single time. However, the required liveness property in Chapter 7 is that red cars (and blue cars) get to enter the bridge infinitely often. In other words, it is always the case that a car eventually enters. This is exactly the condition expressed by progress properties. We can now restate those for the single lane bridge in linear temporal logic as:

assert REDCROSS  = []<>red[ID].enter
assert BLUECROSS = []<>blue[ID].enter
assert CROSS = (REDCROSS && BLUECROSS)

The CROSS property is defined as the conjunction of REDCROSS and BLUECROSS and permits these properties to be checked at the same time. The Büchi automaton for the negation of REDCROSS is depicted in Figure 14.4.

Figure 14.4. REDCROSS Büchi automaton.

In a parallel composition, * synchronizes the transition it labels with all other transitions in the model, i.e. excluding actions red[1].enter and red[2].enter, but including those labeled by the silent action. It can be seen that the always part of the assertion is captured here by the non-deterministic choice on * which means that at any point in a trace, the automaton can move to state 1.

It could be argued that REDCROSS and BLUECROSS are too weak a specification of the required liveness since they are satisfied if either car 1 or car 2 crosses infinitely often. For example, the properties can be satisfied if car 2 never crosses. This is because, as mentioned previously, a set of actions is treated as a disjunction and so the property REDCROSS is:

assert REDCROSS  = []<>(red[1].enter || red[2].enter)

A stronger assertion would be:

assert STRONGRED =  forall[i:ID] []<>red[i].enter

Response Properties

Suppose we wished to assert the liveness property that if a car enters the bridge then it should eventually exit. In other words, it does not stop in the middle or fall over the side! We can specify this property for a car as follows:

assert REDEXIT = [](red[1].enter -> <>red[1].exit)

The corresponding Büchi automaton (for the negation) is shown in Figure 14.5.

Figure 14.5. REDEXIT Büchi automaton.

The property holds for both SingleLaneBridge and CongestedBridge. Although cars may not ever enter the congested bridge, if they do enter, they also exit. Consequently, the property is not violated. This is an extremely common form of liveness property which is sometimes termed a "response" property since it is of the form [](request -> <>reply). Note that this form of liveness property cannot be specified using the progress properties of Chapter 7.

For example, suppose we wish to assert the politeness property of Chapter 7 that we should not enter a room before knocking. We can assert:

assert POLITE = (!enter U knock)

This asserts both the safety property that we cannot have an enter action before a knock action, and also that a knock action should eventually happen. This can be seen clearly from the Büchi automaton for this property depicted in Figure 14.6. The automaton irretrievably enters the acceptance state 1 if an enter action occurs before a knock action occurs. However, if a knock action never occurs, the property is violated because the automaton remains in state 0 which is also an acceptance state.

Figure 14.6. POLITE Büchi automaton.

Given the until operator, we can state the mutual exclusion property of section 14.2.1 using only action fluents:

assert MUTEX_U = []((p[1].enter -> (!p[2].enter U p[1].exit))
                 &&(p[2].enter -> (!p[1].enter U p[2].exit)))

This expresses the required mutual exclusion safety property and, in addition, the liveness property that if a process enters the critical section it should eventually exit. However, the property is considerably more complex than that of section 14.2.1 and is difficult to extend to more than two processes.

The difference with the previous definition of until is that this definition does not insist that q eventually happens. The formula also holds if p is true indefinitely. This means that if we use weak until for the POLITE property:

assert POLITE_W = (!enter W knock)

the property becomes a safety property since it no longer requires that knock eventually happens. The safety property is depicted in Figure 14.7.

Figure 14.7. POLITE_W safety property process.

In the same way, if we replace until with weak until in the definition of the mutex property, it becomes a safety property which generates exactly the same automaton as that depicted in Figure 14.1.

assert MUTEX_W = []((p[1].enter -> (!p[2].enter W p[1].exit))
                 &&(p[2].enter -> (!p[1].enter W p[2].exit)))

In general, there is no need to distinguish between safety and liveness properties when using FLTL to specify properties. Since the safety check is more efficient than the connected component search used in checking general FLTL properties, the LTSA generates a safety property process if it detects that a property is only a safety property. In fact, determining whether a Büchi automaton can be transformed to a safety property process is non-trivial and the LTSA does not guarantee to perform this transformation for all automata that could be reduced.

It should be noted that we could have specified the liveness property that was included in MUTEX_U in the original MUTEX_N property as follows:

assert EXIT_N = forallforall[i:1..N][](p[i].enter -> <>p[i].exit)
assert MUTEX_LIVE = (MUTEX_N && EXIT_N)

MUTEX_LIVE expresses the same property for N processes that MUTEX_U does for two. In fact we can parameterize assertions as follows:

assert MUTEXP(M=2)
       = []!(exists [i:1..M-1] (CRITICAL[i] && CRITICAL[i+1..M]))
assert EXITP(M=2)
       =  forall[i:1..M] [](p[i].enter -> <>p[i].exit)
assert MUTEX_LIVEP(P=2)
       = (MUTEXP(P) && EXITP(P))

<> p ≡ True U p
     [] p ≡ ! <> ! p
      p W q ≡ []p || (p U q)

assert True  = rigid(1)
assert False = rigid(0)

assert Even(V=3) = rigid(V/2 == 0)

By "next instant" in the above definition, we mean when the next action occurs – this includes silent actions. For example, the assertion:

assert SEQ = (a && X b && X X c)

requires that in the initial instant of system execution the action a occurs followed by the action b, followed by the action c. To check for this sequence, the property process shown in Figure 14.8 is generated:

Figure 14.8. SEQ property process.

In fact, this form of property is not very useful. If we were to refine or extend our system (using, say, parallel composition and interleaving) such that actions could occur inbetween a, b or c then the property would no longer hold. This is because next time refers to precisely the time at which the next action occurs, whether silent or not. Consequently, it makes finer distinctions than the observational equivalence that is preserved when we minimize processes. As such, it is rarely used in property specification. In addition, it can prohibit the use of partial order reduction, a technique that can dramatically reduce the time taken to check an FLTL property.

We can simplify the problem by considering that each database stores only a single data item and by restricting the range of data values that can be stored.

const N     = 3            // number of nodes
range Nodes = 1..N
set   Value = {red, green, blue}

We model the communication between database nodes using the PIPE from section 11.1.1 that models a one-slot buffer:

set S = {[Nodes][Value]}
PIPE  = (put[x:S] -> get[x] -> PIPE).

The updates that circulate round the ring are pairs consisting of the identity of the originating node and the value of the update. For example, [1]['red] is an update from node 1 with the value red. The model for each node is as follows:

NODE(I=0)
       = NODE['null][False],    // initially null value and not updating
     NODE[v:{null,Value}][update:Bool]
       = (when (!update) local[u:Value]      // local update
        -> if (u!=v) then
               (change[u] -> put[I][u] -> NODE[u][True])
            else
               NODE[v][False]
        |get[j:Nodes][u:Value]              // update [j][u]
        -> if (!update) then
               CHANGE(j,u);NODE[u][False]    // update and pass on
            else if  (I==j ) then
               (passive -> NODE[v][False])   // complete update
            else if (i>j) then
               CHANGE(j,u);NODE[u][False]    // priority update
            else
               NODE[v][update]               // discard
        ).

     CHANGE(J=0,U='null)
       = (change[U] -> put[J][U] -> passive ->END).

Whenever a node changes the value of its stored data value, it signals this with the action change[u] and whenever an update is complete the node signals passive. The constants True and False are defined in the usual way:

const False = 0
const True  = 1
range Bool  = False..True

The composite process for the database ring model is:

||DATABASE_RING
        = (node[i:Nodes]:NODE(i) || pipe[Nodes]:PIPE)
          /{forall[i:Nodes] {
              node[i].put/pipe[i%N+1].put,
              node[i].get/pipe[i].get}
           }.

Overall, the safety property required of the database model is as follows: when there are no updates in progress, the valuesheldateachnodeshouldbeconsistent. A node that is not engaged in an update signals passive. There can be no updates in progress if all nodes are passive, and the system is said to be quiescent. We can capture the state in which a node is passive by means of the following fluent:

fluent PASSIVE[i:Nodes]
             = <node[i].passive, node[i].change[Value]>

The fluent holds for a node from the time that it signals passive until the time that it signals a change of value. The following assertion captures the quiescent property:

assert QUIESCENT = forall[i:Nodes] PASSIVE[i]

To describe the consistency property, we need to be able to make propositions about the value held by a node as follows:

fluent VALUE[i:Nodes][c:Value]
          = <node[i].change[c],node[i].change[{Value{[c]}}]>

The fluent VALUE is true for a node i and value c if the node has previously changed to the value c and has not yet changed to some other value in the set consisting of Value with c removed. Using this fluent, we can define consistency as the proposition that there exists a value such that each node has that value:

assert CONSISTENT
       = exists[c:Value] forall[i:Nodes] VALUE[i][c]

The required safety property for the database ring system can now be succinctly expressed by the following assertion, which requires that it is always the case that when the system is quiescent, then it must be consistent.

assert SAFE = [](QUIESCENT -> CONSISTENT)

The model we have described does indeed satisfy this property. The reader should replace line 14 of the NODE process with:

else if (/* i>j */ True) then

to obtain an instructive counterexample illustrating the problem of concurrent updates. This modification disables the priority-based conflict resolution in the model.

We have specified the required safety property for the model which ensures that it does not get into a bad state; however, we must also check that the model eventually and repeatedly gets into a good state. The good state for our model is quiescence and the required liveness property is therefore

assert LIVE = []<>QUIESCENT

which is satisfied by our model.

assert WITNESS_LIVE = !LIVE

Violation of LTL property: @WITNESS_LIVE
     Trace to terminal set of states:
           node.1.local.green
           node.1.change.green
           node.1.put.1.green
           node.2.get.1.green
           node.2.change.green
           node.2.put.1.green
           node.2.passive       PASSIVE.2
           node.2.local.red     PASSIVE.2
           node.3.get.1.green   PASSIVE.2
           node.3.change.green  PASSIVE.2
           node.3.put.1.green   PASSIVE.2
           node.1.get.1.green   PASSIVE.2

node.1.passive       PASSIVE.1 && PASSIVE.2
           node.3.passive       PASSIVE.1 && PASSIVE.2 && PASSIVE.3
     Cycle in terminal set:
           ... ... . .
     LTL Property Check in: 281ms

ONE_UPDATE = (node[Nodes].local[Value] -> END).
     ||DATABASE_RING_ONE = (DATABASE_RING || ONE_UPDATE).

ONE_UPDATE = (node[Nodes].local[Value] -> ENDED),
     ENDED      = (ended -> ENDED).

Violation of LTL property: @WITNESS_SAFE
     Trace to terminal set of states:
           node.1.local.blue
           node.1.change.blue  VALUE.1.blue
           node.1.put.1.blue   VALUE.1.blue
           node.2.get.1.blue   VALUE.1.blue
           node.2.change.blue  VALUE.1.blue && VALUE.2.blue
           node.2.put.1.blue   VALUE.1.blue && VALUE.2.blue
           node.2.passive      PASSIVE.2
                            && VALUE.1.blue && VALUE.2.blue
           node.3.get.1.blue   PASSIVE.2
                            && VALUE.1.blue && VALUE.2.blue

node.3.change.blue  PASSIVE.2
                    && VALUE.1.blue && VALUE.2.blue && VALUE.3.blue
           node.3.put.1.blue   PASSIVE.2
                    && VALUE.1.blue && VALUE.2.blue && VALUE.3.blue
           node.1.get.1.blue   PASSIVE.2
                    && VALUE.1.blue && VALUE.2.blue && VALUE.3.blue
           node.1.passive      PASSIVE.1 && PASSIVE.2
                    && VALUE.1.blue && VALUE.2.blue && VALUE.3.blue
           node.3.passive      PASSIVE.1 && PASSIVE.2 && PASSIVE.3
                    && VALUE.1.blue && VALUE.2.blue && VALUE.3.blue
     Cycle in terminal set:
           ended      PASSIVE.1 && PASSIVE.2 && PASSIVE.3
                    && VALUE.1.blue && VALUE.2.blue && VALUE.3.blue
     LTL Property Check in: 31ms