# Tag Info

5

In parallel computing, the threads can talk to each other and exchange information during the computation. In nondeterminism, the only "communication" between threads is that we compute the OR of all possible computation paths. This is much more limited. If you simulate nondeterminism by spawning parallel computations for every nondeterministic choice, you ...

3

Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ordering. Total ordering although more compact cannot tell whether two operations are concurrent or causally dependent.

3

This is not a matter of terminology: they're related, but different concepts. A consensus algorithm is one that allows all the participants in a distributed system to choose a value from a set in such a way that all the participants choose the same value. A solution to the consensus problem is a distributed algorithm that has the following properties: At ...

2

In this context, the rendezvous would mean "a bunch of threads meeting together" instead of people. Rendezvous is a method of synchronisation in which at least two threads "meet". In other words, each thread that reaches the rendezvous point waits until all other threads have reached the same point before proceeding. In the context of Distributed ...

2

Sure. If you have a distributed system with N machines, you can always run the centralized algorithm on machine 1 and let machines 2..N sit idle. If you're asking whether all sequential algorithms can be parallelized, that's an open question, but it's believed that the answer is no: see the NC complexity class. As Wikipedia states, there are probably ...

2

Since the processes can only receive message from their adjacent neighbors, we could first have the all the processes propagate the maximum values through the grid in downward direction in parallel. Similar to a one dimensional array in which we have to find the maximum value. But here, we do that in parallel for n columns of processes. After this, the ...

2

Unicode is a suitable encoding for most scripts because it includes characters from all the scripts. The analog would be an instruction set architecture that includes instructions from all processors. This would be huge and impractical to implement whether in hardware or in software. It would even be contradictory: how do you reconcile an architecture with ...

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

I think I've found an answer, so will post here what I have. My proof seem to cover both scenarios I've mentioned. I still think their proof is incomplete. But in case I'm wrong, I would love to be corrected. Similar to them assuming there is $e'$ outgoing from $F_1$, I assumed there was $e'$ outgoing from $F_3$ that is in $\hat{F_{1}}$, of lower weight ...

1

From Wiki: Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing. It is inherent type of algorithm to be run independently with no requirement ...

1

The authors' goal is to rule out protocols that work for every possible input. Hence, in their proof by contradiction, they can assume that the protocol works correctly on every input. The specification of an algorithm should include all constraints on the possible inputs. For example, binary search assumes that the input array is sorted. The specification ...

1

Yes, your intuition is correct, for all the reasonable models of computation that I'm familiar with. If it weren't, then we could take a single machine and have it simulate a cluster of n nodes, increasing the cost by only a factor of n. So, if you had an algorithm that ran on a cluster of n nodes faster than T/n, you'd get an algorithm that runs on a ...

1

The paper's specification for the phase 2(b) of the algorithm, which is how an acceptor responds to an accept message is the following: If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n. This means that acceptors are allowed ...

1

Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows. Consider two processes $P_i$ and $P_k$ who entered critical sections at moments $e$ and $f$, correspondingly, requested them at moments $e'$ and $f'$, and exited at moments $e''$ and $f''$. At moment $e$ process $P_i$ have received a confirmation from $P_k$....

1

I believe the purpose is to fulfill the first condition of entering the critical section (site $S_i$ must receive a message from all other sites with timestamp greater than its own request) in case some other site never requests to enter the critical section. If $S_i$ sends a critical section request to $S_j$, but $S_j$ never requests the critical section ...

1

Composable means we can check for each object separately and exactly if the property applies to all of them separately then it applies to the whole of them at once. To show that sequential consistency is not composable we can use an example where the ordering implied by the projections on one object contradicts the ordering implied by the projection on an ...

1

If you're looking for a single model that describes all relevant aspects of your system, you'll have a hard time. And building the model will take as much effort as implementing the system itself, if not more. Therefore, break the system down into different aspects, and consider different modelling techniques for each. Examples for aspects might be: The ...

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