Re: [tlaplus] TLAPS, first steps

[Stephan Merz <stephan.merz@xxxxxxxxx>]

Hello,

there are two problems: the fundamental one is that what you are trying to prove is not true. Use TLC to check the temporal property

[][\A p \in P : v[p] # NV /\ Next => v = v']_v

(which is what step <1>3 asserts) for sets of model values P <- {pp, qq} and V <= {a, b} and have a look at the counter-example. It is all too easy to get carried away by what looks like a good idea; use TLC as extensively as you can to make sure that what you are trying to prove actually has a chance of being true.

The second one is that you wrongly identify the peer p that appears in the invariant and the peer pp that appears in the definition of Act1. That's why TLAPS rejects the proof of step <2>q – you showed the assertion only for Act1!(p,vv), but you need to prove it for Act1!(pp,vv), for some arbitrary pp \in P.

Below is a proof of your invariant. I needed to assume the type correctness invariant so that the proof for the EXCEPT _expression_ went through.

For your reduction to work, you'll also have to establish that NV \notin V – the TLAPS module contains a utility lemma to that effect.

Regards,

Stephan

–––

THEOREM TypeOK => StableIndInv
  <1>1. SUFFICES ASSUME NEW p \in P, v[p] # NV, Next, TypeOK
                 PROVE  v[p] = v'[p]
        BY DEF StableIndInv
  <1>4. CASE Act1
        <2>1. ASSUME NEW pp \in P, NEW vv \in V, Act1!(pp,vv)
              PROVE v[p] = v'[p]
              <3>1. CASE p = pp  BY <3>1, <2>1, <1>1
              <3>2. CASE p # pp  BY <3>2, <2>1, <1>1 DEF TypeOK
              <3>q. QED BY <3>1, <3>2
        <2>q. QED BY <1>4, <2>1 DEF Act1
  <1>5. CASE Act2
        BY <1>5 DEF Act2
  <1>q. QED BY <1>1, <1>4, <1>5 DEF Next

LEMMA NV_not_V == NV \notin V
BY NoSetContainsEverything DEF NV

On 8 Apr 2019, at 07:02, Karolis Petrauskas <k.petrauskas@xxxxxxxxx> wrote:

Hello,

I'm trying to write my first proofs in TLAPS, and get stuck.
In the attached file is the simplified version of the specification.
It was constructed to illustrate that problematic part of the proof.

The specification describes a system, where some variable should not change after it was set.

CONSTANT P \* A set of peers.

CONSTANT V \* A set of values
VARIABLE v
NV == CHOOSE nv : nv \notin V
Init == v = [p \in P |-> NV]
Act1 == \E pp \in P, vv \in V :
          IF v[pp] = NV
          THEN v' = [v EXCEPT ![pp] = vv]
          ELSE UNCHANGED v
Act2 == UNCHANGED v
Next == Act1 \/ Act2
Spec == Init /\ [][Next]_v
TypeOK == v \in [P -> V \cup {NV}]

The property I'm trying to prove is formulated as follows:

Stable == \A xp \in P, xv \in V: [] ((v[xp] = xv) => [] (v[xp] = xv))

I managed to prove "Spec => [] TypeOK", and for "Spec => Stable" I'm now try to prove an inductive Invariant:

StableIndInv == \A p \in P : v[p] # NV /\ Next => v[p] = v'[p]

The attempt that looks closest to the proof is the following:

THEOREM Attempt1 == StableIndInv
  <1>1. SUFFICES ASSUME NEW p \in P
                 PROVE  v[p] # NV /\ Next => v[p] = v'[p]
        BY DEF StableIndInv
  <1>2. SUFFICES ASSUME v[p] # NV
                 PROVE  Next => v[p] = v'[p]
        OBVIOUS
  <1>3. SUFFICES ASSUME Next
                 PROVE  v = v' \* Here v[p] reduced to v.
        OBVIOUS
  <1>4. CASE Act1
        <2>1. ASSUME NEW vv \in V
              PROVE Act1!(p, vv) => v = v'
              <3>2. CASE v[p] = NV BY <1>2, <3>2
              <3>3. CASE v[p] # NV BY <1>2, <3>3
              <3>q. QED BY <2>1, <3>2, <3>3
        <2>q. QED BY <1>4, <2>1 DEF Act1
  <1>5. CASE Act2
        BY <1>5 DEF Act2
  <1>q. QED BY <1>3, <1>4, <1>5 DEF Next

The problem (as I see it) is that I cannot relate <1>4 with its proof (<2>q or <2>1?).

I think the question is: how to prove that Act1!(p, vv) implies Act1.

In the attached file there is another attempt to prove this invariant (Attempt0),

but for me the Attempt1 looks closer to what it should be.

The same property was proved trivially for a specification, were variable

v had a value (v \in V) instead of function (v \in [P -> V]).

It would be very helpful to get some directions or comments.

Thank you in advance
Karolis Petrauskas

--
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 post to this group, send email to tlaplus@xxxxxxxxxxxxxxxx.
Visit this group at https://groups.google.com/group/tlaplus.
For more options, visit https://groups.google.com/d/optout.
<TestStable.tla>

--
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 post to this group, send email to tlaplus@xxxxxxxxxxxxxxxx.
Visit this group at https://groups.google.com/group/tlaplus.
For more options, visit https://groups.google.com/d/optout.