Skip to main content
38 votes
Accepted

Why are directed graphs important?

Recalling that a directed graph is a graph where the edges have an associated direction with them. Using a directed graph you can represent asymmetrical relationships between nodes, while in ...
dariodip's user avatar
  • 864
11 votes
Accepted

Why does RAID-5 require an additional disk for parity blocks?

I think you've misunderstood what the parity data is. They're not parity checks, so it's not true that "each parity block is specific to each disc it belongs to." The parity data is to allow recovery ...
David Richerby's user avatar
5 votes

Why are directed graphs important?

Directed graphs do exist. As mentioned in the comments, Directed Acyclic Graphs (DAGs), in particular, are tremendously useful in many computational tasks such as the compiling of code. Also, its ...
Cort Ammon's user avatar
  • 3,351
4 votes
Accepted

What is the algorithm for Blockchain's Byzantine Fault Tolerance?

Actually the differences are more intricate than that. A problem here might be that the properties of "blockchains" are not very well specified and the term is used for a wide variety of things (going ...
Leonidaz0r's user avatar
3 votes
Accepted

Impossibility for Byzantine Generals Problem where $n \leq 3m$

In the synchronous model of communication, there are $n$ agents which share a clock. In each round of communication, each agent sends an arbitrary message to each other agent, and then receives the ...
Yuval Filmus's user avatar
3 votes

Why are directed graphs important?

The beginnings of topological sorting (a fundamental operation on directed acyclic graphs) lie in networks of dependencies in project management, specifically the PERT method. Kahn and Lasser both ...
KWillets's user avatar
  • 1,274
2 votes

Why are directed graphs important?

Answer: From the OP I deduce that the question is actually related to SDGs (Signed Directed Graphs). So here is my answer which addresses basic directed graphs then leads on to SDGs. Directed ...
SDsolar's user avatar
  • 133
2 votes

Two Generals' Problem - Thought Experiment

Let's say $a$ has gotten its second confirmation while $b$ only has one confirmation. $a$ sends an ack to $b$ to tell $b$ it has received the second message. Now, by your rule $a$ should start ...
proof-of-correctness's user avatar
2 votes
Accepted

Why is a threshold determined for Byzantine Fault Tolerance of an "Asynchronous" network? (where it cannot tolerate even one faulty node)

The answer has to do with tracking the precise assumptions that are made in these different results. In short, while both results assume asynchrony, the "impossibility of distributed consensus with ...
Caleb Stanford's user avatar
2 votes

What is the difference between masking and tolerating failures?

The source of your misunderstanding may be that you think the excerpt contains a list of methods to handle system failures that are mutually exclusive. Masking and tolerating failures often happen ...
Kyle Jones's user avatar
  • 8,101
1 vote

Do arbitrary/Byzantine failures include omission failures and timing failures?

Arbitrary failure means exactly what it says. It means that the failing process should be treated as if an opponent is choosing the process's behavior to try to break your system. Other types of ...
Aaron Rotenberg's user avatar
1 vote

Proof in the "Reaching Agreement in the Presence of Faults"

What is important about the paragraph above are the few lines that proceed it in the proof. This is all under the context of "First note that if q is nonfaulty". If we know that q is ...
cypher's user avatar
  • 11
1 vote

Two Generals' Problem Definition

A lot of misunderstanding is caused by explaining the problem as an ongoing process. It's a lot easier to understand if one simply considers the possible states that the generals can be in. Assume the ...
Ray Butterworth's user avatar
1 vote

Two Generals' Problem Definition

Whenever you think you have solved the two general problems, there is only 1 thing you need to do to find why your solution is wrong. Take every step s_1...s_n of your algorithm and treat it as the ...
elcapitozz's user avatar
1 vote
Accepted

Enforcing application layer consensus on top of a distributed consensus protocol

You've asked multiple questions here. I'll answer the first one. Typically consensus means that all the honest participants have the same view of the state of the system. There's not necessarily a ...
D.W.'s user avatar
  • 162k
1 vote

Is there a usable implementation of PBFT?

Not necessarily NFS, but Hyperledger used PBFT for their blockchain platform. This is a Go implementation: https://github.com/hyperledger-archives/fabric/tree/master/consensus/pbft That is an old ...
Ron's user avatar
  • 131
1 vote

Byzantine generals problem with signed messages (Lamport)

According to the paper 1 Generally speaking, Byzantine consensus considers the problem of reaching agreement among a group of n parties, among which up to f can have Byzantine faults and perform ...
nm1300's user avatar
  • 11

Only top scored, non community-wiki answers of a minimum length are eligible