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 ...
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 ...
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
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
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
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 ...
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 ...
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 ...
5
You might be interested in these papers:
The LOCKSS system
Publius: A robust, tamper-evident, censorship-resistant web publishing system
The Eternity Service
The Free Haven Project: Distributed Anonymous Storage Service
Freenet: A Distributed Anonymous Information Storage and Retrieval System
Tarzan: A Peer-to-Peer Anonymizing Network
Anonymizing Censorship ...
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
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'
39.8k7 gold badges105 silver badges170 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible
