Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
2
votes
0answers
25 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
14 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
37 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
15 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
13 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
45 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
13 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
31 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
96 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
9 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
14 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
37 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
23 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....
1
vote
1answer
28 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
15 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
33 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
111 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
23 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
146 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
80 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?
0
votes
1answer
37 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
69 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
42 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
238 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
35 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
28 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
30 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
51 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 ...
2
votes
0answers
23 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 ...
1
vote
1answer
48 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 ...
1
vote
1answer
98 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 ...
2
votes
0answers
37 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
1answer
47 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?
...
1
vote
1answer
29 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 ...
0
votes
1answer
230 views
Vector clock :why Singhal Kshemkalyani differential technique require FIFO for message passing?
Singhal–Kshemkalyani’s differential technique is based on the
observation that between successive message sends to the same process,
only a few entries of the vector clock at the sender process ...
2
votes
0answers
65 views
Why is a primary node needed in pBFT algorithm for consensus?
Why is primary needed in pBFT algo? Since many issues of viewchange etc. come up because primary may be faulty - is it possible to have a version of pBFT which doesn't have nodes assigned as primary? ...
2
votes
1answer
83 views
What are the recents topics of research that combine both systems research and theoretical computer science?
I am an undergraduate majoring in Computer Science and Mathematics.
For my undergraduate research, I would like to work on something that lies in the overlap between systems research and theoretical ...
0
votes
0answers
92 views
How is Eventual Consistency (EC) better than Strong Consistency (SC) when N = 3, R=W=2 when SC gives better consistency gurantee in same config?
In dynamo paper, it says that in production most of the users set N = 3, R = 2 and W = 2.
...
0
votes
0answers
42 views
Is this Paxos example valid?
In this demonstration of the Paxos algorithm, it seems that prep(4) makes use of $\{p_4, p_5, p_6, p_7\}$ and accept(4, yellow) ...
2
votes
0answers
93 views
Byzantine generals (n=3, m=1)
Leslie Lamport describes a algorithm to come to consensus for the case for n>3*m, there m is the number of traitors in ...
1
vote
0answers
47 views
Strong Uniform Total Order vs Weak Uniform Total Order
The definition for SUTO and WUTO is the following:
Suto
If some process TODelivers some message m before message mʹ, then a process TODelivers mʹonly after it has TODelivered m.
And for WUTO
...
2
votes
0answers
95 views
What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?
After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages ...
3
votes
1answer
134 views
Impossibility of Distributed Consensus with One Faulty Process
I'm reading Fischer et al.'s Impossibility of Distributed Consensus with One Faulty Process, and I don't quite follow 2 points:
The first is in the proof of Lemma 3, pg. 378:
Otherwise, $e$ was ...
0
votes
1answer
25 views
Bloom Filter which does not fit in RAM [closed]
Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?
0
votes
0answers
30 views
BFT algorithm perfo
Understand that BFT algorithms are always prepared for the worst possible circumstances and pays a price for this in terms of speed.
Can one reasonably make the statement / assessment that non BFT ...
1
vote
1answer
110 views
How to compare distributed systems and big data
Are there scientific papers that compare distributed systems and big data processing systems?
Big data processing systems can be batch processing systems or streaming big data processing systems.
A ...
1
vote
0answers
29 views
Tendermint Consensus - Resilient up to 1/3 of Byzantine participants
Tendermint Consensus is resilient for up to 1/3 of Byzantine participants.
Question: What actually happens after when the network hits the threshold of byzantine actors? Forking happens? Does ...
2
votes
1answer
89 views
Async Distributed Algorithm Time Complexity
In theory of distributed systems, I understand message complexity and time complexity are common performance measures, with the first being the number of messages sent in the overall execution of the ...
3
votes
0answers
222 views
Even distribution algorithm
Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. ...
