3
$\begingroup$

I'm reading several papers about different broadcast algorithms. Most of them are designed for crash stop model but they also consider contamination scenarios.

For example for a Causal Atomic Broadcast when a faulty process fails to delivers messages in order and then starts broadcasting other messages based on its inconsistent state which causes inconsistent state in other correct processes.

The above is just an example why a specific process could have such a weird behavior although our failure model is crash stop. Follwoing paper describes it more.

A Modular Approach to Fault-tolerant Broadcasts and Related Problems. V. Hadzilacos and S. Toueg, Distributed Systems, 97-145, 1993.

See here section 3.11 (page 22) for more sophisticated example. This is really confusing to me. Why do we don't consider this type of failure as byzantine failures? In crash stop model a single failure should result in a crash. A faulty process can NOT continue to run without crashing. What am I missing?

$\endgroup$
  • $\begingroup$ I'm confused about what you are asking. "Causal Atomic Broadcast" is a goal, not a failure model, so it seems like you are conflating two unrelated things. Exactly what failure model are you asking about? Can you edit the question to clarify? Also, I suggest you include references to one or more examples of the papers that you think illustrate this (title, author, where published, and link to free pdf if available). $\endgroup$ – D.W. May 24 '17 at 20:46
  • $\begingroup$ @D.W. Added paper information $\endgroup$ – Majid Azimi May 26 '17 at 7:04
2
$\begingroup$

I think you are confusing the failure model with the correctness goals of a protocol.

  • A failure model specifies what kinds of things can go wrong (i.e., what kinds of failures the protocol is designed to deal with and promises to be able to handle).

  • A correctness goal describes what properties the protocol promises to provide (i.e., what properties it needs to achieve, to qualify as correct).

We then analyze whether a particular protocol meets a particular correctness goal in a particular failure model. For example, protocol might achieve the correctness goal in one failure model but not in another.

Example of failure models include crash-only; or Byzantine failures; or others. See Sections 2.3 and 2.6 for examples of kinds of failures. A failure model would specify which of those failures are in scope (and thus, implicitly, which are out of scope).

An example of a correctness goal is "Causal Broadcast" or "Atomic Broadcast" or "Causal Atomic Broadcast". For instance, the correctness goal that we call "Causal Broadcast" is that the protocol must ensure Causal Order for all delivered messages (see Section 3.3 of the paper you mention). There might be a protocol that achieves Causal Order in the presence of crashes but not in the presence of Byzantine failures.

With that understanding, Section 3.11 of your paper starts out with an example of a failure that can be problematic. That's a type of failure that isn't just a crash. Yes, it could be considered an instance of a Byzantine failure. However, it is also a more specific type of failure; one can articulate a more specific failure model that is more constrained than arbitrary Byzantine failures, but broader than just crashes, and which includes that failure as the sort of failure that can occur. It may be useful to think about what is achievable in that intermediate failure model. There are more failure models in the world than just "crash stop" and "Byzantine".

$\endgroup$
  • $\begingroup$ Let me ask it this way: If a process is running under crash-stop model and some algorithm specifies that process should deliver m before n. Since this process is faulty it doesn't deliver m but delivers n. Can a process fail like this in crash-stop model? The confusing part is that I'm considering this type of failure as Byzantine but the paper classifies it in crash failure. $\endgroup$ – Majid Azimi May 26 '17 at 15:53
  • 1
    $\begingroup$ @MajidAzimi, I'm not an expert in my area, but my understanding is that that can't happen in a crash-stop model. However: I didn't find anywhere in Section 3.11 where the paper classified that as falling within a crash-stop failure model. Going by Section 2.3, that sounds like it is not a crash failure, but it is a Byzantine failure. $\endgroup$ – D.W. May 26 '17 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.