3 ms·

On slide 10, faulty hardware introduces a standing wave onto a bus. Two CPUs are nodes, two at antinodes, causing a 2-2 disagreement in the state of the system.

On slide 10, faulty hardware introduces a standing wave onto a bus. Two CPUs are nodes, two at antinodes, causing a 2-2 disagreement in the state of the system. Yet, the slide goes on to argue this is a software problem? It was my impression that Byzantine tolerant systems required agreement among ⅔ of the nodes; if the system is split 50/50, how can even a tolerant system not fail? (Or rather, is it the difference between failing gracefully and failing spectacularly, and the slide fails to elaborate on exactly how the system failed? But I don't see how we can expect this to succeed.)

deleted 9y ago
[deleted]
jfoutz 9y ago
I kinda think thats the point. Not exactly a software problem, but an information theory problem. If you need to tolerate 2 failures, you need 6 machines.
- Normal_gaussian 9y ago
  5 machines. Even numbers of machines introduce a higher failure likelihood for no greater tolerance.
  - jfoutz 9y ago
    You're thinking majority not Byzantine fault tolerance. 2/3 have to agree.
    - nickpsecurity 9y ago
      Many of us in high-assurance systems have witnessed triple, modular redundancy fail. I started saying 3 out of 5 for that reason. May be same for other commenter. I also want where possible for the computers to be in different locations, using different hardware, and with different developers working against same API.
      - vitus 9y ago
        Yes, but those aren't Byzantine failures. Byzantine failures present with incorrect values, not simply the absence of a value (as seen by a total hardware failure). See the abstract in Lamport's original paper introducing the Byzantine generals problem [0]. We also see a similar issue in error correction -- an introductory undergrad course might teach this via Lagrange interpolation [1], where you need only n+k of the coefficients in the presence of erasure errors, but n+2k in the general case (where n is the size of the actual message, and k is the maximum number of errors to correct). [0] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/The-Byzantine-Generals-Problem.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [1] https://inst.eecs.berkeley.edu/~cs70/fa14/notes/n8.pdf https://inst.eecs.berkeley.edu/~cs70/fa14/notes/n8.pdf
        nickpsecurity 9y ago
        Partial hardware failures exist. The wrong values start going through the system. A bit flip is easiest example. NonStop has been countering both partial and total HW failures in their design a long time now.
gizmo686 9y ago
I am not sure if it is refering to the NASA incident you are refering to, but a situation consistent with said failure is described here [0] (section 5.3), although it seems like it still assumes some background I do not have to fully understand it. In the situtation described in my link, there were 4 data sources, and 4 processors. A byzantine fault occurred with the link from one of the data sources to the processors. This cascaded into a failure of the entire 4 processor system when it fell into a 2:2 split. In concept, the processors could have communicated with each other and detected a disagreement in one of the four data sources. The software bug is that a fault with one of the data sources cascaded into a fault with the entire processing unit. In a correctly functioning system, the fault should have been contained to just the one data source. That is, the problem should have been no worse then simply losing the bus entirely. Assuming there was sufficient redundancy across the buses, the system could have continued functioning properly despite the fault. However, because the software did not correctly handle the fault, any other redundancy became useless. [0] https://www.cs.indiana.edu/classes/p545-sjoh/post/lec/fault-tolerance/Driscoll-Hall-Sivencrona-Xumsteg-03.pdf https://www.cs.indiana.edu/classes/p545-sjoh/post/lec/fault-...

deleted 9y ago

[deleted]

jfoutz 9y ago

I kinda think thats the point. Not exactly a software problem, but an information theory problem. If you need to tolerate 2 failures, you need 6 machines.

Normal_gaussian 9y ago
5 machines. Even numbers of machines introduce a higher failure likelihood for no greater tolerance.
- jfoutz 9y ago
  You're thinking majority not Byzantine fault tolerance. 2/3 have to agree.
  - nickpsecurity 9y ago
    Many of us in high-assurance systems have witnessed triple, modular redundancy fail. I started saying 3 out of 5 for that reason. May be same for other commenter. I also want where possible for the computers to be in different locations, using different hardware, and with different developers working against same API.
    - vitus 9y ago
      Yes, but those aren't Byzantine failures. Byzantine failures present with incorrect values, not simply the absence of a value (as seen by a total hardware failure). See the abstract in Lamport's original paper introducing the Byzantine generals problem [0]. We also see a similar issue in error correction -- an introductory undergrad course might teach this via Lagrange interpolation [1], where you need only n+k of the coefficients in the presence of erasure errors, but n+2k in the general case (where n is the size of the actual message, and k is the maximum number of errors to correct). [0] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/The-Byzantine-Generals-Problem.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... [1] https://inst.eecs.berkeley.edu/~cs70/fa14/notes/n8.pdf https://inst.eecs.berkeley.edu/~cs70/fa14/notes/n8.pdf
      - nickpsecurity 9y ago
        Partial hardware failures exist. The wrong values start going through the system. A bit flip is easiest example. NonStop has been countering both partial and total HW failures in their design a long time now.

gizmo686 9y ago

I am not sure if it is refering to the NASA incident you are refering to, but a situation consistent with said failure is described here [0] (section 5.3), although it seems like it still assumes some background I do not have to fully understand it. In the situtation described in my link, there were 4 data sources, and 4 processors. A byzantine fault occurred with the link from one of the data sources to the processors. This cascaded into a failure of the entire 4 processor system when it fell into a 2:2 split. In concept, the processors could have communicated with each other and detected a disagreement in one of the four data sources. The software bug is that a fault with one of the data sources cascaded into a fault with the entire processing unit. In a correctly functioning system, the fault should have been contained to just the one data source. That is, the problem should have been no worse then simply losing the bus entirely. Assuming there was sufficient redundancy across the buses, the system could have continued functioning properly despite the fault. However, because the software did not correctly handle the fault, any other redundancy became useless. [0] https://www.cs.indiana.edu/classes/p545-sjoh/post/lec/fault-tolerance/Driscoll-Hall-Sivencrona-Xumsteg-03.pdf https://www.cs.indiana.edu/classes/p545-sjoh/post/lec/fault-...