# Tag Info

## Hot answers tagged fault-tolerance

37

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 undirected graph we can represent only symmetrical relationships. Practically, using a directed graph you can represent: Road networks (using a directed graph you ...

11

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 from a failed disc. Let's go back to RAID-4 for a second, and assume we have three discs: discs $0$ and  $1$ are data and disc $2$ is parity. "Parity"...

5

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 worth noting that most directed graph algorithms can be used in the undirected case simply by replacing each undirected edge with two directed edges. The dual of ...

3

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 as far as simple databases) for marketing. So let's see what is out there. When you are designing a fault tolerant system there are multiple properties to ...

3

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 message sent her by every other agent. A protocol for byzantine agreement on $n$ agents supporting $m$ byzantine agents is a communication protocol for the ...

3

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 cite PERT in their papers and base their examples on it, eg A PERT network of 30,000 activities can be ordered in less than one hour of machine time. Online ...

3

The paper you cited is exploring the consequences of the question "what if datacenter network bandwidth was free?" There are two reasons you might care about data locality. One is latency and the other is bandwidth. The workloads they are looking at (mostly) don't care about latency, and they've made bandwidth irrelevant, hence locality doesn't matter. (...

2

----I'm not sure if this should be my answer. Many thanks to hengxin. It does explain my confusion, and may be helpful to others seeing the question---- I failed to realise that there are 2 types of unreliable messages, - some are different for each lieutenant, (eg 'eX' in round 1) - others are the same for all lieutenants (I will denote these as 'S') the ...

2

As you are probably well aware, it is provably impossible to reach consensus if a majority of the peers are faulty, malicious, or dishonest, if we assume they are all fully connected (as is typically the assumption for distributed systems). If you are imagining that for some reason honest peers are better-connected than faulty/malicious peers, well, there ...

2

Maybe this is what confuses you -- mixing the byzantine agreement problem (broadcast: where there is one transmitter and multiple receivers) and the byzantine consensus (where every party starts with an input, and if all have the same input, this should also be their output). The bound of at most half traitors stems from the consensus requirement. Say we ...

2

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 graphs are widely utilized in fault-tree analysis in industrial systems. As you eliminate causes of a fault you follow the directed graph to explore other ...

2

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 one faulty process" requires a stronger form of liveness and determinism, and that makes consensus impossible. 1. Impossibility of Distributed Consensus with One ...

2

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 simultaneously depending on the interface one part of a system presents to another. Example: a word processor application might only care whether a document was ...

1

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 failure, such as omission failures and timing failures, are special cases of this. They are relevant because certain algorithms only guarantee correct results in ...

1

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 guarantee that this state is "correct" in any sense (some protocols might also provide that guarantee, but it is in some sense a separate or additional request)....

1

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 repo, they seem to be currently using a new repo with implementations in other languages as well, however I haven't gone through it in detail: https://gerrit....

1

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 arbitrarily. There exist a few variant formulations for the Byzantine consensus problem. Two theoretical formulations are "Byzantine broadcast" and "Byzantine ...

1

When tackling such problems, think in general terms. Researchers have studied the impact of malicious peers in numerous papers. Most of these systems should work. However, define your problem clearly. Ex: What are the malicious peers trying to do in this case? do you want to: protect your system from unwanted outsiders (security), protect your data from ...

1

I found the answer consulting the book "Distributed System : Principles and Paradigms" (Andrew S. Tanenbaum - Maarten Van Steen). First of all it is possible to continue just because 3PC is non-blocking protocol by definition. A processor can reach the state “PRE-COMMIT” only if the coordinator was in state “PRE-COMMIT” (thus each processor sent a COMMIT ...

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