[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [tlaplus] Fairness and either statement



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


On Tuesday, July 6, 2021 at 9:13:48 AM UTC-7 hwa...@xxxxxxxxx wrote:

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

On 7/6/2021 1:34 AM, Stephan Merz wrote:
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

On 1 Jul 2021, at 14:53, p.to...@xxxxxxxxxxxxxxxxx <p.to...@xxxxxxxxxxxxxxxxx> wrote:

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



--
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...@xxxxxxxxxxxxxxxx.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/932afbd1-f11a-4be3-a69a-ac1289ad7e11n%40googlegroups.com.

--
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...@xxxxxxxxxxxxxxxx.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/12016527-CCB4-422F-965E-0D71CA237511%40gmail.com.

--
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+unsubscribe@xxxxxxxxxxxxxxxx.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/743b047f-7830-4805-8dc6-2635f1b29c80n%40googlegroups.com.