Comments (6)
Huang's algorithm has been added (https://github.com/tlaplus/Examples/tree/master/specifications/Huang). Additionally, we could try and find a refinement mapping s.t. Huang refines AsyncTerminationDetection.tla.
from examples.
from examples.
Thanks: 5ef47ac
from examples.
A first attempt showing refinement of AsyncTerminationDetecting by Huang. It is not a refinement because ATD doesn't allow pending decrement when an inactive Leader in Huang receives the last weight back.
Node ==
0..Cardinality(Procs) - 1
M ==
CHOOSE f \in [ Node -> Procs ]: IsInjective(f)
ATD ==
INSTANCE AsyncTerminationDetection
WITH
terminationDetected <- TerminationDetected,
active <- [ n \in Node |-> active[M[n]] ],
pending <- [n \in Node |-> Len(msgs[M[n]]) ],
N <- Cardinality(Procs)
ATDSpec ==
ATD!Spec
THEOREM Spec => ATDSpec
Action property line 63, col 20 to line 63, col 32 of module AsyncTerminationDetection is violated.
The behavior up to this point is:
1: <Initial predicate>
/\ active = {L}
/\ weights = (L :> "1")
/\ msgs = << >>
/\ Terminated = FALSE
/\ TerminationDetected = FALSE
2: <SendMsg line 48, col 5 to line 53, col 27 of module Huang>
/\ active = {L}
/\ weights = (L :> "1/2")
/\ msgs = (L :> <<"1/2">>)
/\ Terminated = FALSE
/\ TerminationDetected = FALSE
3: <IdleLdr line 72, col 5 to line 74, col 33 of module Huang>
/\ active = {}
/\ weights = (L :> "1/2")
/\ msgs = (L :> <<"1/2">>)
/\ Terminated = FALSE
/\ TerminationDetected = FALSE
4: <RcvLdr line 78, col 5 to line 81, col 27 of module Huang>
/\ active = {}
/\ weights = (L :> "1")
/\ msgs = << >>
/\ Terminated = TRUE
/\ TerminationDetected = TRUE
from examples.
The definition of Wakeup(i) in AsyncTerminationDetection could be changed to
/\ pending[i] > 0
/\ / UNCHANGED active
/ ~ active[i] /\ active' = [active EXCEPT ![i] = TRUE]
/\ pending' = [pending EXCEPT ![i] = @ - 1]
/\ UNCHANGED terminationDetected
allowing an inactive receiver to either become active or remain passive. (It should then probably be renamed to Receive.)
from examples.
Ah, GitHub formatting ... maybe this works better:
/\ pending[i] > 0
/\ \/ UNCHANGED active
\/ ~ active[i] /\ active' = [active EXCEPT ![i] = TRUE]
/\ pending' = [pending EXCEPT ![i] = @ - 1]
/\ UNCHANGED terminationDetected
from examples.
Related Issues (20)
- Submodules vs. copying specs into the repo HOT 2
- `ctl[p]` is never equal `"req"` in specifications/SpecifyingSystems/Liveness properties HOT 6
- GitPod & Codespaces - make sure bitrot hasn't set in
- Add TLC models for all specs for which it's viable
- Add some Apalache models HOT 5
- Bakery-Boulangerie specs don't satisfy `DeadlockFree` or `StarvationFree` liveness properties HOT 1
- Can't come up with working model for cbc_max or spanning HOT 1
- Liveness and Safety properties fail in SpanTreeRandom.tla HOT 11
- Deactivate macOS CI runners? HOT 3
- Add optional fields to manifest.json recording total and unique states for each model
- Add proof checking time to manifest details
- EWD998 model checking failure when running TLC from outside tlaplus/examples repo HOT 5
- Properties `Unforg_Ltl` and `Corr_Ltl` of `aba_asyn_byz` hold if all nodes *start* in `V0` or `V1` HOT 2
- Question about the specification of reliable broadcast algorithm by Bracha & Toueg (1985) HOT 8
- CI workflow fails on ubuntu HOT 7
- Do not suppress TLC output HOT 3
- Possible TLC regression on specifications/ewd998/EWD998ChanID.cfg HOT 7
- ERROR in specifications/SpecifyingSystems/Composing/CompositeFIFO.tla: In evaluation, the identifier in is either undefined or not an operator. HOT 1
- Remove deadlock flag in manifest.json in favor of `CHECK_DEADLOCK` in config file HOT 4
- Install TLA+ unicode converter into gitpod and codespaces HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from examples.