Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
305
questions
1
vote
0answers
14 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
23 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
0answers
9 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
55 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
10 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
15 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
16 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
9 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
17 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
38 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
19 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
9 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
110 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
65 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
21 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
13 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
65 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
11 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
25 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
27 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
19 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
41 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
16 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
25 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
49 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
20 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
39 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 ...
1
vote
2answers
286 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
12 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
20 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
46 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
24 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
63 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
16 views
Distributed maximal matching from vertex coloring
How to use a $\Delta +1$ vertex coloring to find a maximal matching in a distributed graph.
1
vote
0answers
43 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.
3
votes
1answer
133 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 ...
1
vote
0answers
25 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 ...
0
votes
1answer
205 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?
1
vote
1answer
132 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?
1
vote
1answer
51 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 ...
4
votes
0answers
78 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 ...
0
votes
0answers
44 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 ...
1
vote
1answer
411 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?
0
votes
0answers
43 views
Proof of impossibility result for distributed consensus
I am reading the classic paper by Fisher, Lynch, Merritt "Easy impossibility proofs for distributed consensus problems", and cannot understand the model they are using. It seems it was already ...
0
votes
1answer
32 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 ...
0
votes
0answers
34 views
Start with highest ID in bully algorithm?
I try to implement the bully algorithm for leader election in a distributed system.
The pseudo code says to send an election message to all nodes with a higher ID then the own node and to wait for ...
0
votes
0answers
83 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 ...
