Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
316
questions
1
vote
0answers
20 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 ...
-1
votes
0answers
32 views
What does Consensus mean?
I am trying to understand what exactly "consensus" means inside the "distribute computing" world. Do someone has a good definition? Furthermore, is "consensus" a synonym of "consensus number"?
0
votes
1answer
39 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 ...
4
votes
0answers
51 views
What distributed consensus algorithms don't rely on a time source?
I'm looking for information about distributed consensus algorithms that:
maintains a consistent transaction log across all healthy nodes
has similar high-availability properties to Paxos (i.e. not ...
0
votes
0answers
16 views
Consensus without majority
I am new to distributed computing but after a quick look at Paxos and Raft it is clear that for those algorithms to work majority of the servers should be up and running.
So is it fundamental to ...
-3
votes
1answer
98 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 ...
-1
votes
1answer
27 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
...
0
votes
1answer
22 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?
0
votes
0answers
13 views
Ideal time complexity in analysis of distributed protocol
I need some explanation about the definition of ideal time complexity.
My textbook says:
The ideal execution delay or ideal time complexity, T: the execution
delay experienced under the ...
1
vote
1answer
40 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 ...
2
votes
0answers
37 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 ...
1
vote
1answer
18 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 ...
0
votes
0answers
16 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
vote
0answers
17 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 ...
1
vote
0answers
30 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 ...
0
votes
1answer
20 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 ...
1
vote
0answers
60 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 ...
0
votes
0answers
12 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
1answer
18 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 ...
1
vote
0answers
23 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
0answers
12 views
Time-slice Equalizing Algorithm
I have a requirement for which I am trying to write an algorithm and struggling a bit conceptually with. This seems like it should be a common-ish type problem so I imagine there is a name/standard ...
0
votes
0answers
19 views
Consistency CAP vs ACID
I understand that the consistency property specifies what values can be read, depending on what has been written before. For instance, if we consider a simple abstract read/write service. It enjoys ...
0
votes
1answer
54 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 ...
1
vote
1answer
31 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 ...
0
votes
0answers
11 views
Graph with arboricity a, all verteces are marked active
So I came across this problem that I would like help solving/explaining:
We have a graph with arboricity a (can be partitioned to a min of a trees).
We run the following algorithm on the graph:
- All ...
2
votes
2answers
111 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 ...
0
votes
0answers
17 views
Can't understand this example of convergecast addition from a book
In the book Distributed Computing: A Locality-Sensitive Approach by David Peleg, in chapter 3, Broadcast and convergecast, in section 3.4.2 Global function computation, examples are given for global ...
1
vote
1answer
75 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 ...
0
votes
0answers
29 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 ...
1
vote
0answers
18 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 ...
0
votes
0answers
23 views
Questions while I'm making distributed key-value store
I'm CS student.
I'm currently trying to make distributed key-value store.
Since I'm new to distributed system concept.
I'm struggling with sort of concrete implementation and methodology to apply ...
1
vote
0answers
66 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 ...
0
votes
0answers
12 views
How to detect a consensus is BFT or not?
Can we divide consensus algorithms into BFT (Byzantine Fault
Tolerant) and non-BFT ?
If so, How to detect a consensus is BFT or non-BFT ?
Is there any non-BFT consensus algorithm example ?
0
votes
0answers
26 views
Data structure to know if something was calculated
There's the typical interview question about how to create a distributed and scalable URL shortener.
One of the issues is to know if a URL was shortened already or not. There's a special data ...
2
votes
0answers
29 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 ...
0
votes
0answers
25 views
What is the relationship between Consistency Models and Consensus Algorithms?
I know that:
Each replication technique should follow a consistency model. A consistency model defines a set of rules for the order of the write and read operations. In some replication techniques ...
0
votes
0answers
47 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)
0
votes
0answers
9 views
How to make use of opponent policy on designing ours in multi-agent learning
I'm currently working on a multi-agent reinforcement learning. The setting is a cooperative multi-agent system with a stationary assumption on the opponent policy. Suppose I have the model of the ...
0
votes
0answers
17 views
Distributed selection (window) algorithm
For n records distributed amongst m processes/nodes (no shared memory) I'd like to accomplish the following for some given ranking criteria
find the rth item.
find the rth to r+cth items for some ...
1
vote
0answers
30 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 ...
2
votes
1answer
59 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 ...
0
votes
0answers
23 views
Need a layman's example of Linearizable Consistency model
As far as I understand,
Linearizable Consistency model is a Data-centric and Strong consistency model.
Data-centric means:
- All clients experience the consistency
- All clients access the same ...
0
votes
0answers
40 views
Should I use lamport logical clock or vector clock or something else?
simplified use case:
I have 3 nodes where each node sends a message to the other two always(so a message won't be sent from one to another node. It would always be sent to two other nodes) and every ...
2
votes
2answers
431 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 ...
0
votes
0answers
13 views
How is consensus impossible under FLP even when no fault exists at that moment?
Could some give an illustration of the following sentence?
In fact, for every purported consensus protocol that guarantees agreement and validity, there is some execution in which there are no ...
0
votes
0answers
23 views
What does asynchronous communication in FLP impossibility comprise of?
Conditions:
(i) Is it just async networks, that is, messages might be arbitrarily delayed?
(ii) Does it also require that the processors should be running at different speeds?
(iii) Is the absence ...
1
vote
1answer
63 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 ...
0
votes
1answer
27 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....
2
votes
1answer
94 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, ...
0
votes
0answers
20 views
Distributed maximal matching from vertex coloring
How to use a $\Delta +1$ vertex coloring to find a maximal matching in a distributed graph.
