Fairness and either statement

143 views
Skip to first unread message

p.to...@studenti.unipi.it

unread,
Jul 1, 2021, 8:53:03 AM7/1/21
to tlaplus
Hi all, i don't know how to use the either statement in pluscal with fairness condition on the options of the either or statement. I have tried the following example with a label for each option of the statement but it doesn't seems to work:

begin example:

    while TRUE do

        either

            branch1:

                set := {1};

        or

            branch2:

                set := {2};

        end either;

        later:

            skip;

    end while;


and the formula prop2 == <>(set={1}) doesn't hold true, the system cycle over all branch2 options. I have tried to add the fairness in the tla translated specification putting an /\ SF_vars(branch1) but the problem persists, here is the tla+ translation from pluscal: 

VARIABLES set, pc


(* define statement *)

prop2 == <>(set={1})



vars == << set, pc >>


ProcSet == {"test"}


Init == (* Global variables *)

        /\ set = {}

        /\ pc = [self \in ProcSet |-> "example"]


example == /\ pc["test"] = "example"

           /\ \/ /\ pc' = [pc EXCEPT !["test"] = "branch1"]

              \/ /\ pc' = [pc EXCEPT !["test"] = "branch2"]

           /\ set' = set


later == /\ pc["test"] = "later"

         /\ TRUE

         /\ pc' = [pc EXCEPT !["test"] = "example"]

         /\ set' = set


branch1 == /\ pc["test"] = "branch1"

           /\ set' = {1}

           /\ pc' = [pc EXCEPT !["test"] = "later"]


branch2 == /\ pc["test"] = "branch2"

           /\ set' = {2}

           /\ pc' = [pc EXCEPT !["test"] = "later"]


test == example \/ later \/ branch1 \/ branch2


Next == test


Spec == /\ Init /\ [][Next]_vars

        /\ WF_vars(Next)

        /\ SF_vars(test)

        /\ SF_vars(branch1)


someone can help? thanks


Stephan Merz

unread,
Jul 6, 2021, 2:34:36 AM7/6/21
to tla...@googlegroups.com
Hello,

requiring strong fairness for the branch1 action won't help because the non-deterministic decision of which branch to enter is taken earlier (at the "either" statement labeled "example"). This is one of the cases where the intended fairness condition has to be expressed in TLA+. You probably want to write something like

  /\ SF_vars(example /\ pc' = [pc EXCEPT !["test"] = "branch1"])
  /\ SF_vars(example /\ pc' = [pc EXCEPT !["test"] = "branch2"])

in order to express that both branches will be taken infinitely often if execution arrives infinitely often at the "either" statement.

Hope this helps,
Stephan

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/932afbd1-f11a-4be3-a69a-ac1289ad7e11n%40googlegroups.com.

Hillel Wayne

unread,
Jul 6, 2021, 12:13:48 PM7/6/21
to tla...@googlegroups.com

IMO needing to put fairness on a non-deterministic decision is one of the points where you should be considering switching to TLA+ over using PlusCal.

H

Leslie Lamport

unread,
Jul 6, 2021, 1:04:14 PM7/6/21
to tlaplus
Fairness is probably the part of TLA+ that most people find hardest to
understand.  This is not a problem with TLA+.  Most other formalisms
don't have this problem because they simply can't express the kind of
fairness that you need.  The fundamental reason fairness, and liveness
in general, are hard to understand is that they are properties of
infinite behaviors, and people have trouble understanding the
infinite.  For example, their minds are usually blown by "Hilbert's
hotel", which is always full but always has room for another guest
because it has an infinite number of rooms.  (You can look it up on
the web.)

If you learn PlusCal and enough about TLA+ to understand how to
express the fairness properties you will need, you should have no
trouble learning to write TLA+ specs.  You will then have the freedom
to use either PlusCal or TLA+, whichever is best for an application.
You can also use PlusCal together with TLA+ specifications of
fairness.  You can write a PlusCal algorithm with no fairness
requirements, which will be translated to a specification named Spec.
You can then add, after the translation, the definition

   FairSpec == Spec /\ some fairness conditions

and use FairSpec as your specification.  (Don't modify the definition
of Spec because your modifications will disappear the next time you
run the translator.)  You can also put some fairness conditions in the
PlusCal code and put additional fairness conditions that can't be
expressed easily in PlusCal in the definition of FairSpec.

Incidentally, you can always express any TLA+ fairness conditions in
PlusCal.  However, this often requires changing the process structure
of the PlusCal code.  In your example, that can be done by replacing
the process that executes either branch1 or branch2 with two
processes: one that executes branch1 and one that executes branch2.
When you understand TLA+, you will understand that processes are not
inherent in an algorithm but represent a particular way of writing the
TLA+ formula that is the algorithm.

Leslie

Huailin

unread,
Jul 6, 2021, 1:25:57 PM7/6/21
to tla...@googlegroups.com
"Fairness is probably the part of TLA+ that most people find hardest to
understand.  This is not a problem with TLA+.  Most other formalisms
don't have this problem because they simply can't express the kind of
fairness that you need. "

The fundamental reason fairness, and liveness
in general, are hard to understand is that they are properties of
infinite behaviors, and people have trouble understanding the
infinite. 

I do love this above so much and kept smiling(or crying) when drinking my morning coffee(home made), and cannot agree more. 
Yes, the "infinite often/many" plays the key.


Huailin

unread,
Jul 6, 2021, 1:31:42 PM7/6/21
to tla...@googlegroups.com
My high-school daughter finds it hard to understand why there are the same amount of even numbers as the nature numbers...

Also, why "0.99999...." equal to 1. Because: too much...:-)

On Tue, Jul 6, 2021 at 10:04 AM Leslie Lamport <tlapl...@gmail.com> wrote:

Andrew Helwer

unread,
Jul 6, 2021, 3:35:54 PM7/6/21
to tlaplus
I feel like the programmer in me understood fairness a lot better when I learned how liveness is modelchecked. TLC tries to find "lasso"-shaped state traces as counterexamples to your desired liveness properties - lasso-shaped as in the trace loops back to some state found earlier in the trace (in the case of stuttering, this is just looping at the final state). Since all liveness properties are of the form <>P, finding a lasso where P is not satisfied suffices as a counterexample. Asserting fairness is a way of disallowing certain lasso counterexamples. If you want to disallow a stuttering counterexample, you use weak fairness. If you want to disallow a non-stuttering lasso counterexample, you use strong fairness. A loose analogy is that assuming weak fairness assumes that the system will eventually do something (as opposed to sitting there doing nothing), and assuming strong fairness assumes the system will eventually make the correct decision at a branch (usually fail or not fail).

I guess this isn't a full account of fairness (it doesn't really account for what it means when fairness itself is the liveness property you want to prove) but it has worked well for all the systems I've specified in TLA+ so far.

Andrew
Reply all
Reply to author
Forward
0 new messages