Comments (8)
Tagging the spec authors: @konnov @banhday @josef-widder
from examples.
@lemmy Thanks!
from examples.
Hi @lduranovic99 , could you please clarify which spec you are referring to. I guess there might be several and the encoding of faults may differ, so to answer your second question, I want to be sure we are on the same page ;-)
Regarding the first concern, this encoding originated from our previous work on parameterized model checking threshold automata, e.g. here. This method only works on symmetric systems, so we couldn't capture a special process (the broadcaster) in an efficient manner. At the same time, we wanted to verify the threshold functionalities (t+1, n-t under resilience conditions like n>3t). Thus, we have chosen to capture the effect of the broadcaster in the initial state:
- all processes have 0: e.g., the broadcaster is correct and didn't choose to send any message.
- all processes have 1: e.g, the broadcaster is correct and thus sends to everyone
- mixed inputs: the broadcaster is faulty and sense to some (those with 1)
(Of course the "all 0s" and "all 1s" also capture the scenario where the broadcaster is "faulty", but sends or does not send consistently to everyone.)
From our initial states, a process sends echo if and only if it sends echo in executions the corresponding execution with a broadcaster. To formalize the argument, I guess I would define projections of traces that abstract away the broadcaster, and show that there is trace equivalence to the traces of the spec.
from examples.
Hi @josef-widder! Thanks for the response. You can find the specific file that I was looking at here.
I think your explanation for why this specification makes sense (in terms of the broadcaster) makes sense to me, although I would be curious to see what this formalization argument for matching traces obtained by the two versions of the algorithm would look like.
I'm still very interested in the behavior of the faulty hosts, and what your thoughts are on how well this model captures the behavior of Byzantine hosts.
from examples.
Thanks to your initial question, I found a bug in the encoding. I proposed a fix in #81.
However, the overall encoding is OK, and indeed it captures the non-determinism on the correct receiver that is due to faulty senders. Consider this condition that guards the increment of the counter at process i
of received echo messages nRcvdE[i]
The counter can only be incremented if it smaller than the sum of
- the number of echo messages sent by correct processes
- the number of Byzantine processes
Potentially, Byzantine processes can be assumed to have sent any message, and the adversary has the control whether and when to deliver these messages. Even if this action is enabled, it may never trigger, that is, nRcvdE[i]
may never exceed nSntE
.
So this kind of encoding captures the effect Byzantine nodes have on correct ones, rather than the actions of Byzantine nodes.
from examples.
@josef-widder @lduranovic are there any changes that need to be made to the example spec or are we good to close this issue?
from examples.
I think we can close the issue as it was mostly a question on modelling. The problem that we then found was fixed in #81.
from examples.
Yeah, thanks for asking! I will go ahead and close it with this comment then.
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
- 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.