Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
399
questions
1
vote
0
answers
19
views
Arbitrary fault abstraction in 'Reliable and Secure Distributed Programming'
In the book by Cachin, Guerraoui, Rodrigues they discuss an arbitrary fault abstraction. It seems to me that this abstraction does not include crashes in its behavior. I think this because they ...
- 163
1
vote
0
answers
51
views
What are the correlation between Actor model and Reactive Programming
Could anyone explain the difference/relation between the Actor model and Reactive programming?
It seems that they are located at different levels of abstraction - one can design the interaction ...
- 11
1
vote
1
answer
346
views
Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?
So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used ...
- 121
5
votes
1
answer
132
views
What distributed consensus algorithms don't rely on a time source?
I'm looking for information about distributed consensus algorithms that:
maintain a consistent transaction log across all healthy nodes
have similar high-availability properties to Paxos (i.e. not ...
- 251
-3
votes
1
answer
817
views
What is the difference between masking and tolerating failures?
Distributed Systems 5ed by Coulouris says on p21-22
1.5.5 Failure handling
Detecting failures: Some failures can be detected. For example, checksums can be used to detect corrupted data in a ...
- 4,785
0
votes
1
answer
428
views
Do arbitrary/Byzantine failures include omission failures and timing failures?
Distributed Systems 5ed by Coulouris says on p68
2.4.2 Failure Models
Omission Failures ...
Arbitrary Failures
The term arbitrary or Byzantine failure is used to describe the worst
...
- 4,785
0
votes
1
answer
115
views
How to convert a centralized algorithm to a distributed algorithm?
Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis?
- 23
1
vote
1
answer
90
views
How do I use message passing to find the maximum of all values in a grid?
I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly ...
- 111
2
votes
0
answers
79
views
Leader election in synchronous ring with unreliable communication channels
As a part of my Distributed Systems course I am required to provide an algorithm that is able to elect a leader in a synchronous bidirectional ring, where every message that is sent may be lost (lets ...
- 21
1
vote
1
answer
55
views
Implementing reliable pairwise average in distributed systems
Consider an asynchronous and unreliable distributed system. Each node has a value. Suppose that p and q are two neighbor nodes of the system (p_val and q_val are the values of p and q respectively). p ...
- 261
0
votes
0
answers
19
views
How to divide services and capacities in a graph?
Given a graph where some nodes can provide some services with x,y,z... capacities. A node connected to multiple nodes needs to divide these services to the connected nodes and these nodes themselves ...
- 1
1
vote
0
answers
64
views
Byzantine Generals Problem - Regular Set of Neighbors
Going through Lamport's paper, I'm a little confused by the second part of the regular set of neighbors definition.
A set of nodes $\{i_1, \ldots, i_p\}$ is said to be a regular set of neighbors ...
- 21
1
vote
0
answers
106
views
Byzantine Generals Problem - Oral and Signed Messages
Having just read through Lamport's paper, I was hoping someone could clarify a few things on the Oral and Signed message algorithms.
Why do we have to run $OM()$, recursively by $m$? If a majority of ...
- 21
1
vote
1
answer
40
views
Guaranteed existence of a blocking set in the accept definition of Stellar
In the SCP, condition 2 of the accept definition allows a node to vote for one statement and later accept a contradictory one. Condition 2 assumes the existence of a v-blocking set which has not only ...
- 21
1
vote
0
answers
116
views
Paxos algorithm, accept phase
From the wiki https://en.wikipedia.org/wiki/Paxos_(computer_science)
If a Proposer receives enough Promises from a Quorum of Acceptors, it needs to set a value v to its proposal. If any Acceptors had ...
- 36
0
votes
0
answers
27
views
Given two or more nodes in a network, is it possible to determine the one-way link latencies between two nodes that share a bi-directional connection?
We already know that detecting the one-way latency between only two nodes is impossible.
However, if I have a number of nodes in the same subnet that all know about each other, can measure round-trip ...
1
vote
1
answer
57
views
Distributed algorithm can be executed in a single process
Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency ...
- 111
3
votes
1
answer
397
views
Resetting Vector clocks in distributed systems
I understand that vector clocks are preferred over lamport clocks because sometimes lamport clocks cannot account for the casuality and we use extra space to store the timestamps in the vector clocks.
...
0
votes
1
answer
96
views
Distributed Algorithm Problem
Consider a t-resilient read-write shared memory system (0 < t < N) with initial failures only: faulty processes take no steps. How could one give a consensus algorithm in this system? I don't ...
- 101
2
votes
1
answer
84
views
Input distribution in FLP Impossibility
Lemma 2 in "Impossibility of Distributed Consensus with One Faulty Process" is as follows:
LEMMA 2. P has a bivalent initial configuration.
They prove this by showing that the opposite assumption ...
- 123
2
votes
2
answers
141
views
Why is there no extensive Standards Body overseeing ISAs, Bitcodes, Code Representation, etc... as there is in the case of Unicode
There exist a vast array of prominent bitcode formats, each suited for their specific task:
LLVM IR:
This format is build around a XML like binary streams model, designed to be used as a common ...
- 21
1
vote
1
answer
115
views
Where were the ideas of vote, accept and commit phases originally introduced?
In the Stellar Consensus Protocol SCP, the voting procedure follows a 3 phase commit i.e. vote, accept and confirm i.e. see section 5.
Is this a novel introduction or has this been previously been ...
- 21
0
votes
0
answers
165
views
Running Time of Oral Messages Algorithm OM(m) for Byzantine Generals Fault Tolerance
Let us consider a byzantine generals problem assuming:
less than 1/3 of generals are traitors
Oral messages
No Crypto
One solution is the Oral Message algorithm OM(m), m being the maximum number ...
- 101
1
vote
0
answers
28
views
Problem of making entities agree on some wavelength
I remember seeing this problem somewhere before, but don't remember what it's called and can't find it again.
It was presented as two guys having $n$ phones each that don't ring when called. Each ...
- 675
1
vote
0
answers
75
views
A tree-like data structure with rights delegation for distributed computing
Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...
- 11
2
votes
0
answers
43
views
Distributed algorithms for finding n largest elements
It's easy to come up with a simple distributed algorithms for finding the maximum element in a set (totally ordered): Divide and conquer.
There are a few publications that present algorithms for ...
- 141
0
votes
0
answers
101
views
Construction of Omega Network
I understand that we could draw N * N Omega Network,
But can we draw an Omega Network to connect 6 CPUs to 4 memories? (The number of CPUs does not equal the number of memories)
1
vote
0
answers
34
views
Why in the Map Reduce Implementation, why not stream the records to the reducer (via TCP) as they are being produced by the mappers?
In the Map-Reduce implementation, the reducers start when all mappers finish their jobs. Why don't we stream the records from mappers to reducers while they are being processed instead? I think there ...
- 171
2
votes
1
answer
84
views
Distributed MST Construction in O(log log n) Rounds in a Clique
I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5.
It shows by induction on k (phase number), that ...
- 167
5
votes
2
answers
2k
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 ...
- 261
2
votes
1
answer
527
views
How is the literal meaning of "rendezvous" related to its usage in distributed computing?
I am trying to figure out the difference between RPC and Rendezvous. Is it correct that they differ only on their implementation on server side: RPC will involve creating a new process/thread to ...
- 4,785
0
votes
1
answer
51
views
Optimal scalability of a distributed algorithm
What's the optimal scalability of some algorithm when I implement it in a distributed manner?
Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes....
- 171
3
votes
1
answer
399
views
How does paxos algorithm handle partial failures of accept messages?
I've been reading the basic paxos algorithm from the "Paxos Made Simple" paper. I can't understand how paxos algorithm maintains the safety properties under partial failures of the accept messages, ...
- 163
1
vote
0
answers
110
views
How do distributed algorithms for shortest path finding handle negative cycles?
I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
- 167
5
votes
1
answer
939
views
What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?
Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle).
It ...
- 216
2
votes
0
answers
62
views
Why don't RDBMS use a quorum based solution to do failover
For RDBMS viz. MySql, PostgreSql a common solution for scalability and high availability is to run a primary instance as master that is a read-write instance and one or more read replicas. If the ...
- 121
1
vote
1
answer
1k
views
What is a genuine atomic multicast?
What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?
user20691
1
vote
1
answer
352
views
Does the Paxos algorithm use failure detectors?
Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?
user20691
1
vote
1
answer
220
views
Is There An Established Way To Send Code Over a Network?
Let's say I have two computers on a network. I want to write code in some language on machine A, send the code in an efficient way over a network, and run the code on machine B. It seems to me that ...
- 11
4
votes
1
answer
131
views
In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3?
The paper is available here:
https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
The 1st paragraph of lemma 3's proof says
In other words,if event e is applicable to config C,and E is any ...
- 41
0
votes
0
answers
56
views
Under which conditions is it possible to scale a distributed log with checksums?
This question is related to Amazon's QLDB, but my question is about the generic architecture of such a software system. The question arises from the fact that Amazon advertises the service as "highly ...
- 156
8
votes
2
answers
10k
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?
- 327
0
votes
1
answer
55
views
Event-based architecture (in the context of Distributed Systems)
Our course lecture slides divide architectures of distributed systems into:
object based architectures (e.g. typical distributed web application)
resource-centered architectures (e.g. torrents and ...
- 327
2
votes
3
answers
1k
views
What's the difference between strong consistency and sequential consistency?
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
... the result of any execution is the same as if the operations of all
the processors were executed in some ...
- 690
2
votes
0
answers
68
views
Distributed Computing: Persistent Data Structures in Functional Programming versus Wait-Free Data Structures
Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to ...
3
votes
1
answer
212
views
Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?
In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp.
This timestamp is used to order all the events in a distributed system.
The rule ...
- 229
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 ...
- 229
2
votes
0
answers
44
views
Algorithms / heuristics for a distributed sorting problem
The setting:
There's a cluster of $k$ computers (= nodes). For simplicity, assume their hardware is identical.
The network topology can be complicated, but let's simplify and assume it's a clique ...
1
vote
1
answer
60
views
Can a distributed algorithm be serial?
Can a distributed algorithm be serial?
For example if I have 3 distinct agents in a network would an algorithm that looks like this be considered a distributed algorithm?
...
- 626
1
vote
1
answer
35
views
Prominent applications not suited for distributed computing [closed]
In the www I can find a lot of application examples suited for and benefitting a lot from distributed computing.
Question: Are there applications which are not suited for distributed computing? If ...
- 131