14
The following diagram, from a blog post I wrote, is a visual proof that it's impossible:
Notice how the packet arrival times on each side stay the same, even as the one-way latencies change (and even become negative!). The first packet always reaches the server at 1.5s on the server's clock, the second always reaches the client at 2s on the client's clock, ...
12
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 opposite sides of the globe):
if $T_2$ starts to commit after $T_1$ finishes committing, then the timestamp for $T_2$ is greater than the timestamp for $T_1$.
10
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 results by others freely (low cost).
An algorithm is distributed if it is parallel and the tasks run on separate machines (separate address spaces), one task has no ...
8
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:
send msg to Actor137.
2) in FRP the data flow is described declaratively:
For example:
Cell134=Cell185+Cell42.
The message passing is handled by the FRP framework ...
7
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:
This short position paper discusses the fact that, from a teaching point of view, parallelism and distributed computing are often confused, while, when looking at ...
7
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. J. - Legislator
Tωυεγ: Toueg, S. - Legislator
Ωκι: Oki, B. M. - Legislator
∆ωλεφ: Dolev, D. - Farmer
Σκεεν: Skeen, M. D. - Merchant
Στωκµε˘ιρ: Stockmeyer, L. - ...
7
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 Lamport's paper is often called potential causality. It captures all possibilities, often inducing a huge causality graph, and in practice it wrecks the scalability/...
7
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 often must deal with failure (e.g., one machine crashes, one machine starts misbehaving and sending spurious messages, or messages get lost or corrupted). In ...
7
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 of processes accept a value. A majority in these algorithms means that at least $N / 2 + 1$ processes accept a value, where $N$ is the total number of ...
7
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
blocking state by the failure of the coordinator when the
participants are in uncertain state. The participants keep
locks on resources until they receive the ...
7
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 right number. Let's say there are $N > 1$ possible values only one of which is correct at each minute. Then, in a world with only two miners, each minute there ...
6
If two different processors share one memory, each having individual cache, they can end up having two different values in the same address.
Imagine each of two processors has private caches L1 and L2. The cache L3 is shared between both processors. Assume the processor A reads data from address X in L3 to L1 and the processor B reads the same data from the ...
6
In MapReduce you take a big computation and split it up into many small computations that are done in parallel and that don't depend on one another. That way you can use many cores and if one calculation fails, you don't have to redo the entire job, just that small task.
But if you have a problem that can't be broken down into sub-problems that are ...
6
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 to his readers as it does to him. I think for Lamport $a$ could causally affect $b$ actually means something more like information could flow from $a$ to $b$ ...
6
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 remote files. If you already have a list of files, you are unaware of their physical location (e.g., some URL) since you retrieved these files or how they were ...
6
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 crash.
There are several ways to circumvent this impossibility results, by, according to Jennifer Welch; I suggest you to read the linked webpage
changing ...
6
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 "distributed algorithms" from the perspective of "network computing" (think: algorithms that keep the Internet running).
I will use as a ...
6
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 of the vector block is a timestamp chosen by the $i$th computer. In a centralized system you'd use a $N$-vector with $N=1$, so it just reduces to a single ...
6
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 of a multidigraph in which the edges are labelled by events. $\mathscr{C}$ is the set of nodes reachable in any number of steps from $C$ while not following ...
6
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 ...
6
⋃ 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 someExpressionDependingOnJ ranging over all js together", ⋃j someExpressionDependingOnJ means "union the values of all the different instances of ...
5
Totally ordered means that there exists an order relation such that given any two elements, one is greater than the other. In other words, there are no incomparable elements. For example, the real numbers are totally ordered: either $x \le y$ or $y \le x$. Counter-example: set inclusion $\subseteq$ is an order relation, but $\{0\}$ and $\{1\}$ are ...
answered Mar 28 '14 at 17:21
Gilles 'SO- stop being evil'
41k7 gold badges108 silver badges172 bronze badges
5
If you turn an activity-on-node task graph into a partial order (by taking the transitive closure), then the largest independent set of tasks is what you are looking for.
(Taking a topological sort, as suggested in another answer, does not work in general. Consider the series-parallel task graph $((a|b)c)|(d(e|f))$, where $\alpha|\beta$ means parallel ...
5
Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server. Because of the way tract locations are hashed, sequential reads of any blob always walk the tract locator table in the same order. Suppose you have six tract servers and your tract locator table looks ...
5
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 each (process) executes a transaction: Every process can issue as many transactions as they want.
Your understanding of Linearizability ($\textsf{LR}$) is quite wrong. First, for both $\textsf{SR}$ ...
5
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 would cause every item to be re-hashed and nearly every item to move from one computer to another, which could take days.
So instead we use special hash ...
5
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 total number of operations will be higher.
Because of the high variability, and the overall time taken, often distributed algorithms are measured in terms of ...
5
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 ...
answered Mar 19 '19 at 15:34
Gilles 'SO- stop being evil'
41k7 gold badges108 silver badges172 bronze badges
4
The second function is easier to explain: it sends tract $t$ to position $t + h \pmod{n}$, where $h = hash(g)$. The function $t \mapsto t + h \pmod{n}$ is injective (one-to-one), and so every index $i$ gets mapped exactly once (in fact, by $i - h \pmod{n}$).
For the first function, we can think of $t \mapsto hash(g+t)$ as a random function (this is a common ...
4
You are correct: when one processor changes a memory location that is locally cached, then all other processors that are sharing that memory location need to be notified.
So why have local caches? If you didn't then every memory access would be as slow. You want most memory accesses to be fast, so each processor should have its own fast cache. This works ...
Only top voted, non community-wiki answers of a minimum length are eligible