13 votes

External consistency vs linearizability

External consistency doesn't have a fixed meaning. In this context, it has the meaning appearing in the very next sentence in the document: For any two transactions, $T_1$ and $T_2$ (even if on ...
10 votes

Parallel vs Distributed Algorithms

An algorithm is parallel if there are several processes (tasks, threads, processors) working on it at the same time. Often the tasks run in the same address space, and can communicate/reference ...
  • 13.8k
10 votes

Difference between Lamport timestamps and Vector clocks

Summary: Lamport timestamps and vector clocks are both logical clocks, and both provide a total ordering of events consistent with causality. Vector clocks allow you to determine if any two ...
  • 231
9 votes

How do Functional Reactive Programming and the Actor model relate to each other?

I wanna point out how they are different from a practical point of view: 1) actors send messages to other actors, this message passing is described explicitly and imperatively. For example: ...
  • 255
7 votes
Accepted

Who are the legislators of Paxos?

This is an educated guess of the transliterated names I could find in the Paxos paper. Most of these are people mentioned in the paper's references. Λ˘ινχ∂: Lynch, N. - Legislator Φισ∂ερ: Fischer, M. ...
  • 819
7 votes

Distributed vs parallel computing

Here is a recent paper that is worth reading: Michel Raynal: "Parallel Computing vs. Distributed Computing: A Great Confusion?", Proc. Euro-Par 2015, doi:10.1007/978-3-319-27308-2_4 Abstract: ...
7 votes

Happened-before and Causal order

As it has been pointed out by both @kramthegram and @Wandering Logic, event $a$ "happened before" event $b$ does not imply that $a$ has physically caused $b$ (to happen). Such causality used in ...
  • 9,299
7 votes

Parallel vs Distributed Algorithms

One important quantitative distinction is that communication often costs more in distributed computing than in parallel computing. An important qualitative distinction is that distributed algorithms ...
  • 147k
7 votes
Accepted

What is the consensus algorithm that requires an odd number of nodes?

To my knowledge there is no quorum-based consensus algorithm that requires an odd number of nodes (processes). That's because such algorithms don't require a majority in the sense that a higher number ...
7 votes
Accepted

Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

The paper says By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$ Here is a proof: The set of configurations forms the nodes ...
  • 3,245
7 votes
Accepted

Why is Two-Phase Commit (2PC) blocking?

Is it because the cohorts don't employ timeout concept in 2PC? Yes, in one case they can not use a timeout. It is described in the paper too (II.B.1): The Two-Phase Commit Protocol goes to a ...
  • 281
7 votes

Why are forks in the Blockchain eventually resolved?

If we simplify and assume that each miner randomly guesses a hash (as opposed to being more systematic) and we discretize time, say into minutes, then each minute each miner is hoping to "roll" the ...
6 votes
Accepted

Happened-before and Causal order

Note that causality is an undefined term in the paper. Lamport is using it in an informal explanation. He's assuming that could causally affect is an intuitive concept that will mean the same thing ...
6 votes
Accepted

Linearizability and Serializability in context of Software Transactional Memory

About your definitions: The basic idea of Serializability ($\textsf{SR}$) is correct. However, it does not have to constrain itself on the your assumption that ...
  • 9,299
6 votes
Accepted

Does location transparency imply access transparency?

There is certainly a strong dependency between these two properties and many examples will point to this conclusion. Think about an API that needs to use the same operations to access both local and ...
  • 362
6 votes

Consensus problem of distributed systems

The FLP theorem [1] says that It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced ...
  • 9,299
6 votes

Parallel vs Distributed Algorithms

The terms can mean almost anything, but I will try to present here one way in which the terms "parallel algorithms" and "distributed algorithms" are understood. Here we interpret &...
6 votes
Accepted

Are vector clocks useful in centralized systems?

No, there's no need for a vector clock in a centralized system. A vector clock uses a $N$-vector of timestamps, where $N$ is the number of computers in the distributed system and the $i$th component ...
  • 147k
6 votes

Difference between Lamport timestamps and Vector clocks

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 ...
  • 61
6 votes
Accepted

What is the difference between Consensus and Leader Election problems?

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 ...
6 votes
Accepted

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

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 ...
  • 3,481
6 votes
Accepted

Confused between 2 phase locking and 2 phase commit

These are two different things that have two different goals. The two-phase locking protocol is designed to guarantee serializability for transactions that access concurrently a single, centralized ...
  • 769
6 votes
Accepted

Algorithm notation

⋃ is the n-ary union operator, similar to how ∑ is the n-ary addition operator. So, in the same way that ∑j someExpressionDependingOnJ means "add the values of all the different instances of ...
5 votes
Accepted

How to resize a large, distributed hash table?

Yes, after storing many items in a distributed hash table spread over a hundred computers, if hypothetically we used the sort of hash function popular for in-RAM hash table, adding another computer ...
5 votes

How do you compute the time complexity of distributed algorithms?

Time complexity is always measured relative to some model. For example, the $\Theta(n \log n)$ bound on sorting is the number of comparisons performed. If comparisons are not constant time, then the ...
  • 29.3k
4 votes

Distributed vs parallel computing

In the Introduction section of the book [1], the authors provide another perspective (different from the ones in other answers) on the comparison between distributed computing and parallel computing. ...
  • 9,299
4 votes
Accepted

What is the difference between consensus and mutual exclusion in Distributed Systems?

If you have a consensus mechanism, then you can achieve consensus on who owns a critical section, and thus solve mutual exclusion. This is exactly what happens in, say, single-master distributed ...
  • 2,209
4 votes
Accepted

Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

Chord is meant to be used in a distributed system where we need to be concerned with load balancing and handling failures of individual machines. If you try to maintain an AVL tree in a distributed ...
  • 1,028
4 votes
Accepted

Applications of Lamport's Distributed Mutual Exclusion algorithm

Lamport introduced his distributed mutual exclusion algorithm as an example in Lamport, Leslie: Time, Clocks and the Ordering of Events in a Distributed System, Communications of the ACM, 21(7):558-...
4 votes
Accepted

solving large nonlinear systems in parallel

The main point of Krylov-Newton is that it does not require computing and storing the whole Jacobian matrix. It only requires the ability to apply the matrix to a vector. The stardard approach is to ...
  • 1,049

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