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

Re: [tlaplus] Problem with instance substitutions



You may want to take a look at this too: https://github.com/nano-o/M2Paxos

Looks very similar to the spec you are trying to write.

On Sunday, October 7, 2018 at 7:28:10 AM UTC-4, Rodrigo Q. Saramago wrote:
Oh! I'll take a look on that chapter! Thanks!

Em sábado, 6 de outubro de 2018 18:48:33 UTC+2, Leslie Lamport escreveu:
Your spec should not trigger the TLC bug, because that seems to affect
only the instantiation of expressions containing a subscript.  I don't
think TLC will handle your spec, but it should if you rearrange the
conjuncts to satisfy TLC's requirements for a next-state relation,
which are explained in the chapter on TLC in "Specifying Systems".
The superfluous UNCHANGED conjunct will cause no harm.

There should be a bug report on the instantiation problem in

Github.  I haven't looked at very much of the TLC code, and I
don't know where to look for this bug.  But the fact that it seems
to affect only expressions with subscripts should help one find
the problem.

Leslie


On Saturday, October 6, 2018 at 6:50:19 AM UTC-7, Rodrigo Q. Saramago wrote:
Hi Leslie, thank you very much for your suggestion, after watching the lectures I was able to make it works. Here is a simple example that I made to test the solution proposed by Stephan, where I use many instances of consensus, each one to choose on one value:

---------------------------- MODULE SimpleNConsensus ----------------------------
EXTENDS FiniteSets, Naturals

CONSTANT Value, N

VARIABLE consensusInst

ASSUME N \in Nat /\ N > 0

Instances == 1..N

vars == <<consensusInst>>

TypeOK == consensusInst \in [Instances -> SUBSET Value]

C(i) == INSTANCE Consensus WITH chosen <- consensusInst[i]

Init == /\ consensusInst \in [Instances -> SUBSET Value]
        /\ \A i \in Instances: C(i)!Init

Choose(v) == /\ consensusInst' \in [Instances -> SUBSET Value]
             /\ \A i \in DOMAIN consensusInst: v \notin consensusInst[i]
             /\ \E i \in Instances:
                 /\ C(i)!Next
                 /\ consensusInst' = [consensusInst EXCEPT ![i] = @ \cup {v}]
                 /\ \A j \in Instances \ {i} : UNCHANGED consensusInst[j]

Next == \E v \in Value: Choose(v)

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

-----------------------------------------------------------------------------
(***************************************************************************)
(* Safety: At most one value is chosen for all instances                   *)
(***************************************************************************)
Inv == /\ TypeOK
       /\ \A i \in Instances: Cardinality(consensusInst[i]) \leq 1

THEOREM Invariance == Spec => []Inv

-----------------------------------------------------------------------------
(***************************************************************************)
(* Liveness: A non-trivial value is eventually chosen for all instances    *)
(***************************************************************************)
NonTriviality == \A i \in Instances: <>(consensusInst[i] # {} /\ consensusInst[i] \subseteq Value)

LiveSpec == Spec /\ WF_vars(Next)

THEOREM LivenessTheorem == LiveSpec => NonTriviality

=============================================================================
\* Modification History
\* Last modified Sat Oct 06 15:34:11 CEST 2018 by rodrigo
\* Created Wed Oct 03 17:25:53 CEST 2018 by rodrigo


Em sábado, 6 de outubro de 2018 10:51:57 UTC+2, Leslie Lamport escreveu:
If your spec were correct, TLC would not be able to handle it because
of a long-standing bug: it doesn't correctly handle parametrized
instantiation.  I suspect that this bug is not hard to fix, but there
have always been more pressing issues to handle.  It would make a nice
project for someone who wants to help.

About the bug, is there some issue already open for that? Or do you know where in the code, someone interested in helping, could start looking?

And thank you for taking your time on this!

Best

However, your spec seems to have the same error that Stephan
pointed out in Bekir's example.  If you didn't understand Stephan's
explanation, try the one at around 11 minutes 40 seconds of the 5th
TLA+ video lecture.

Leslie