48
I can not help but think: this is divide & conquer, plain and simple!
M/R is not divide & conquer. It does not involve the repeated application of an algorithm to a smaller subset of the previous input. It's a pipeline (a function specified as a composition of simpler functions) where pipeline stages are alternating map and reduce operations. ...
26
Neither actors nor FRP are about streaming. Actors don't even support external configuration of an output stream.
FRP is strongly characterized by its modeling signals and events on a linear timeline, which enables FRP behaviors to compose in a deterministic manner. Actors are strongly characterized by processing messages in non-deterministic order, and ...
23
Roger Wattenhofer's Principles of Distributed Computing lecture collection is also a good place to start.
It is freely available online, it assumes no prior knowledge on the area, and the material is very well up-to-date — it even covers some results that were presented at conferences a couple of months ago.
22
EDIT (March 2014) I should say that I have since worked more on algorithms for MapReduce-type models of computation, and I feel like I was being overly negative. The Divide-Compress-Conquer technique I talk about below is surprisingly versatile, and can be the basis of algorithms which I think are non-trivial and interesting.
Let me offer an answer that ...
17
This is a good question.
It appears that the term server was commonly used already in 1960s. For example, RFC 5, which was published in 1969, already uses the term, and it seems that it was in a common use already back then.
However, the term client in this context seems to be much more recent; the earliest references that I was able to find are from 1978. ...
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, ...
11
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
Both of the books mentioned in the other posts are good, however I like:
Design and Analysis of Distributed Algorithms, Nicola Santoro.
Introduction to Distributed Algorithms, Gerard Tel.
Lynch and Wattenhofer, two big names in Distributed systems theory, focus "a lot" on synchronous systems. On the other hand, Santoro and Tel focuses more on ...
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 ...
9
A good start would by Distributed Systems by Nancy Lynch. It is perhaps a little dated, but nothing is wrong with the book as such. An impossibility result does not change with time.
7
The labels $c_v$ and $c_p$ are relative. So when a node (parent in your example) having $c_v = 1010010000$ receives from its parent (grandparent in your example) an id $c_p = 0010110000$, the difference, as you correctly point out, is in the fifth position.
Now, the total number of bits in the original ids is 10, so representing any index (0-9) will require ...
7
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
All of the mentioned books are awesome, but I recommend you the James Aspnes Notes on Theory of Distributed Systems. It is a very good and up-to-date book that explores theory aspects of distributed systems. It is also free!
I used this notes when I was TA and students were very happy about it. It has many questions with their solutions.
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
I fully agree with you. From a conceptual perspective, there is nothing really new: Map/Reduce was originally known in Parallel Computing as a data-flow programming model. However, from a practical point of view, Map/Reduce as proposed by Google and with the subsequent open-source implementations has also fueled Cloud Computing and is now quite popular for ...
6
Based on the wording of this, it seems to imply that there are n of each buffer
Assuming that each edge in the network graph $G=(V,E)$ corresponds to a bidirectional channel, there are $4|E|$ many buffers in total: For an (undirected) edge $(p_i,p_j)$, we have one pair of in/out buffers for $p_i$ and one pair for $p_j$.
Each state of the processor $p_i$ ...
6
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. - ...
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
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 ...
5
The idea of a routing table in Pastry (and all structured P2P networks) is to minimize its size, while guaranteeing a quicker routing.
The routing algorithm of Pastry goes as follows:
Step A. A node u searches for an object A by firstly looking it up in its leaf set.
Step B. If it was not available, then the query is forwarded to a known node that ...
5
The term can at least be traced back to a publication by Carriero, Gelernter and Leichter from 1986: Distributed Datastructures in Linda[Lin86]. The paper attributes the term to Rob Bjornson (which I believe to be this guy), but only cites personal communication as their mean of learning the term. [Lin86] also refers D. Gelernter: Dynamic global name spaces ...
5
The problem you state is very close to the problem of Byzantine Agreement with faulty links. Yet, it is not clear to me what is the guarantees you seek out of your algorithm.
The algorithm you give does not solve the Byzantine-agreement problem. Specifically, if the party that holds the message is corrupt, and it begins by sending $v_0$ to some player but ...
5
The most widely used formalism is the $\pi$-calculus by Milner, Parrow and Walker. It is an extension of CCS, and comes in many variants, some of which (the asynchronous $\pi$-calculus) attempt to be a formalisation of the actor model. There are now many typing disciplines for $\pi$-calculi, the simplest of which are probably Honda's session types. Such ...
Only top voted, non community-wiki answers of a minimum length are eligible
