Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Tag Info

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 ...

5

Most filesystems and filesystem implementations are designed to be resistant to a loss of power. When you rename a file, with most operating systems, you can expect to always see the file either under its old name or under its new name. If there is any intermediate stage where the file is so to speak half-renamed, the operating system will hide it from you, ...

4

Search for something called a "Journaling File System", of which variants are used on many popular operating systems. The basics of a journaling system are: Record intended change to the journal Make the change This provides basic corruptiong protection in the case of any kind of failure (including the power being lost). If an interruption happens prior/...

4

Your suspicion is correct: under these conditions, there is no way to guarantee a solution. Yours is a consensus problem, and there is a general result that states the impossibility of consensus in an asynchronous network with failures. This result is sometimes known as FLP after its authors (Fischer, Lynch and Paterson) [FLP]. The original consensus states ...

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

Informally, the problem is similar to Sicilian reasoning. Any given agent can only act if it got the original message, it knows that everybody else got the message, it knows that everybody else knows it got the message, and so on. In your model, there is no tool to break this dilemma: all communication is explicit and therefore prone to loss. In addition, ...

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 ...

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

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 ...

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 ...

1

all the papers [...] state that $3m+1$ with only $m$ traitors will definitely give you the correct solution They should actually state that when $3m+1$ then correct algorithms exist, but not all algorithms are correct. Algorithms are like cooking recipes (in fact recipes are algorithms): Consider the problem of baking bread. There are books that tell ...

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