Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
411
questions
72
votes
4
answers
17k
views
What is the novelty in MapReduce?
A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1]
The name is ...
- 72.4k
65
votes
8
answers
72k
views
Distributed vs parallel computing
I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty ...
- 1,183
41
votes
6
answers
10k
views
Clock synchronization in a network with asymmetric delays
Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want ...
32
votes
2
answers
10k
views
How do Functional Reactive Programming and the Actor model relate to each other?
FRP is about streaming events and behaviours through pure functions. The Actor model - at least, as implemented in Akka - is about streaming immutable messages (which can be considered to be discrete ...
- 673
27
votes
7
answers
16k
views
Start learning about Theory of Distributed Systems?
What's the best way that anyone can do to have a good introduction to the theory of distributed system, any books or references, and topics should be covered first and requirements to start learning ...
- 381
23
votes
1
answer
5k
views
How Does Populating Pastry's Routing Table Work?
I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify.
Disclaimer: I'm not a computer science student. I've ...
- 333
21
votes
4
answers
10k
views
Measuring one way network latency
This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is ...
- 5,852
20
votes
1
answer
2k
views
distributed alpha beta pruning
I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see ...
- 301
17
votes
5
answers
6k
views
External consistency vs linearizability
In Spanner, TrueTime & The CAP Theorem, Eric Brewer writes:
One subtle thing about Spanner is that it gets serializability from
locks, but it gets external consistency (similar to ...
- 281
15
votes
1
answer
882
views
All soldiers should shoot at the same time
When I was a student, I saw a problem in a digital systems/logic design textbook, about N soldiers standing in a row, and want to shoot at the same time. A more difficult version of the problem was ...
- 5,994
15
votes
1
answer
811
views
Who are the legislators of Paxos?
In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol.
According to this ...
- 253
14
votes
3
answers
4k
views
What is the origin of the client server model?
I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?
12
votes
2
answers
12k
views
Difference between Lamport timestamps and Vector clocks
Lamport timestamps and vector clocks sound like almost the same thing. Both are used to determine the order of events in a distributed system. What are their key differences?
- 367
10
votes
3
answers
3k
views
Happened-before and Causal order
I'm reading Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" and there's a detail that's bugging me.
Lamport defines the "happened before" partial order, which I ...
- 355
10
votes
1
answer
264
views
Formalisms in concurrent and/or distributed programming?
My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional ...
- 203
10
votes
1
answer
323
views
Can the end-to-end principle be formalized?
In the late 1990s, when I was in graduate school, the paper
JH Saltzer; DP Reed; DD Clark: End-to-end arguments in system design. ACM Trans. Comput. Syst. 2(4):277-288, 1984. DOI=10.1145/357401....
- 17.8k
9
votes
2
answers
4k
views
Why is the commit phase in PBFT necessary?
I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that
PREPARE phase ensures fault-...
- 201
8
votes
2
answers
4k
views
Linearizability and Serializability in context of Software Transactional Memory
I've been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general.
At this ...
8
votes
1
answer
1k
views
Consensus problem of distributed systems
I just started reading about distributed systems for the first time ever. There is a fairly slick proof of the impossibility of consensus in an asynchronous model using some combinatorial topology. On ...
- 121
8
votes
2
answers
125
views
Computer science fields that deal with peer-to-peer systems
I'm an undergraduate and am looking forward to becoming an academic; do the whole PhD stuff and start doing research. I'm interested in a variety of computer science related things but lately P2P ...
- 301
8
votes
1
answer
239
views
Finding a maximal independent set in parallel
On a graph $G(V,E)$, we do the following process:
Initially, all nodes in $V$ are uncolored.
While there are uncolored nodes in $V$, each uncolored node does the following:
Selects a random real ...
- 5,994
8
votes
0
answers
84
views
Distributed Storage for Access and Preservation
My organization wants to maintain multiple copies of data in order to preserve access in the case of localized disasters as well as for the purpose of long term preservation. Are there accepted formal ...
- 585
7
votes
2
answers
3k
views
How do you compute the time complexity of distributed algorithms?
How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(...
- 1,198
7
votes
2
answers
122
views
Algorithm of Communication with Failures
I am interested in Distributed Algorithms especially in communication in network with failures.
I look for the proof of the following randomized algorithm of communication in network with failures. ...
- 3,179
7
votes
1
answer
2k
views
Does location transparency imply access transparency?
In distributed systems theory, I have found the definition that a distributed system requires, among others, location and access transparency.
I was wondering if location transparency does not ...
- 173
7
votes
2
answers
168
views
Theoretical foundations of robust and distributed services
I have the notion of a social network which is robust against malicious attacks from the outside. My vision is a system that is structurally built up as a distributed network of equal servers that ...
- 171
7
votes
1
answer
692
views
Origins of the term "distributed hash table"
I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came ...
- 291
7
votes
1
answer
460
views
Analyzing load balancing schemes to minimize overall execution time
Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given ...
- 12.9k
7
votes
1
answer
1k
views
Vector clocks: Why is it necessary to increment my clock on receiving a message?
Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes.
...
- 219
7
votes
1
answer
848
views
Visualization of Lamport's three-dimensional "space-time diagram" with introduced "tick lines"
In the third page (the third paragraph in the right column) of the paper "Time, Clocks, and the Ordering of Events in a Distributed System" by Leslie Lamport, it says that
The reader may find it ...
- 9,551
7
votes
1
answer
1k
views
How are lamport timestamps useful in practice?
I am reading Lamport's paper titled Time, clocks, and the ordering of events in a distributed system
I understand what's in there more or less, but I am confused whether Lamport timestamps on their ...
- 171
7
votes
2
answers
816
views
Impossibility for Byzantine Generals Problem where $n \leq 3m$
Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance
In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the ...
- 370
7
votes
2
answers
2k
views
6-coloring of a tree in a distributed manner
I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time.
The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse ...
- 3,179
6
votes
6
answers
5k
views
Parallel vs Distributed Algorithms
Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core ...
- 389
6
votes
2
answers
3k
views
Why do you have to worry about cache coherence if you are using shared memory?
Wikipedia says that shared memory comes with lots of costs associated with cache coherence costs. But I thought the whole idea of shared memory is that all the CPUs access the same memory? So if one ...
- 327
6
votes
1
answer
2k
views
Confused between 2 phase locking and 2 phase commit
I understand that both algorithms are very different, but what I don't understand is whether they achieve the same thing in the end. 2PC is for atomic commits and 2PL is for serializable isolation. ...
- 171
6
votes
2
answers
3k
views
What is the difference between Consensus and Leader Election problems?
According to this paper written by Lamport, `selecting a unique leader is equivalent to solving the consensus problem'.
Based on the above quote, my question is: What is the difference between ...
- 271
6
votes
1
answer
2k
views
Why are forks in the Blockchain eventually resolved?
I'm reading Wattenhofer's The Science of the Blockchain. On page 87, he states the following thoerem:
Theorem 7.22. Forks are eventually resolved and all nodes eventually agree on which is the ...
- 960
6
votes
1
answer
518
views
Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)
Please bear with my unhelpful typesetting.
My question is regarding well known FLP paper
Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson
While ...
- 265
6
votes
1
answer
654
views
Why do relational databases use 2PC for distributed transactions over the likes of Paxos?
Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case ...
- 257
6
votes
3
answers
492
views
Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems
The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link ...
- 9,551
6
votes
1
answer
873
views
Lamport Timestamps: When to Update Counters
In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following:
Each process $Pi$ increments $Ci$ between any two ...
- 353
6
votes
1
answer
364
views
per-record timeline consistency vs. monotonic writes
It seems to me that the per-record timeline consistency as defined by Cooper et al. in "PNUTS: Yahoo!’s Hosted Data Serving Platform" mimics the (older?) definition of monotonic writes. From the paper:...
- 291
6
votes
0
answers
95
views
What is 2g-precedence?
I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much ...
user39853
5
votes
2
answers
6k
views
Why is Two-Phase Commit (2PC) blocking?
Can anyone let me know, why 2PC is blocking when the coordinator fails? Is it because the cohorts don't employ timeout concept in 2PC?
Good reference: Analysis and Verification of Two-Phase Commit &...
- 229
5
votes
1
answer
1k
views
Distributed 6-color Vertex Coloring
I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10).
Here is a short description
Idea of the algorithm: We start with color labels that have $\log n$ bits. ...
- 3,179
5
votes
2
answers
2k
views
How to resize a large, distributed hash table?
Many hash table implementations found in programming languages (such as Java's HashMap or Python's dict) dynamically increase the size of the hash table once the number of items reaches a certain ...
- 203
5
votes
2
answers
684
views
solving large nonlinear systems in parallel
I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
- 53
5
votes
1
answer
1k
views
Lamport logical clock: what does partial mean in the concept of `Partial ordering`?
In lamport's paper[1], he define two concept The partial ordering and The totally ordering.
What does partial mean in ...
- 249
5
votes
1
answer
266
views
Can I prove that I have x such that f(x) < c without revealing x?
I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) < c for some real-valued function f and some c of Alice's choosing, so she hires Bob ...
- 153