Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
0
votes
1answer
11 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?
0
votes
1answer
18 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
23 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 ...
3
votes
0answers
37 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
38 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
0answers
27 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
22 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
23 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
16 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
36 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 ...
0
votes
0answers
22 views
Does Cassandra provide strong consistency?
Cassandra is claiming to provide strong consistency, making use of the idea of read/write quorums, as presented in the Dynamo paper.
More concretely, the claim is that if for a specific item:
N is ...
2
votes
0answers
13 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
29 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
47 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 ...
1
vote
0answers
24 views
Algorithms / heuristics for a distributed sorting problem
The setting:
There's a cluster of $k$ computers (= node). 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
41 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
28 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
110 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
43 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
78 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
80 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
25 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
51 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
32 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
50 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
92 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
24 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
27 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
68 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 ...
0
votes
0answers
14 views
Three Phase Commit (3PC): Can a cohort commit because of missed abort during second phase
As a reference, I am reading this:
http://courses.cs.vt.edu/~cs5204/fall00/distributedDBMS/sreenu/3pc.html
Here is the scenario:
All cohorts have received the prepare message and they acknowledged
...
0
votes
0answers
16 views
Byzantine Fault Tolerant - What happens when the threshold of malicious/arbitrary fault is reached?
I understand that through the use of Proof of Work (PoW), Sybil attacks are deterred in public blockchains. The longest chain prevails. Malicious attackers are deterred.
For consortium and/or private ...
1
vote
0answers
27 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
49 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 ...
0
votes
0answers
10 views
Concurrent server with preallocated Threads
Can we implement a mechanism described below with mutex and a condition variable? If yes, then what r the structures, code of the master and slave threads used in it?
Mechanism -" Consider a ...
3
votes
0answers
122 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. ...
1
vote
0answers
24 views
Number of replicas needed for fault tolerance in state machine replication
I am trying to get my head around "State Machine Replication". I understand that it is a way to ensure resilience against failures. I have read that in order to provide fault tolerance against normal ...
2
votes
0answers
54 views
Are Synchronous Message Order and Total Message Order separate concepts?
I am currently studying this book on distributed systems. In the chapter on message ordering the authors appear to use the term total message ordering and synchronous message ordering interchangeably. ...
0
votes
0answers
63 views
a problem with Suzuki-Kasami mutex algorithm
I have some sort of a misunderstanding regarding the Suzuki-Kasami distributed mutex algorithm. I am writing my question here because I failed on gaining access to the original paper.
I will call ...
0
votes
1answer
55 views
Chord protocol - How should I go about mapping nodes to placeholders on the ring?
In the real world, how is a node mapped to the position on the ring,
Each nodes's IP address is hashed using SHA-1 hashing algorithm which will produce this hash - 73.128.154.69 hashed into ...
1
vote
0answers
97 views
bakery algorithm, switching up the condition
I'm currently studying the Bakery Algorithm. I understand it for what it is but now I want to switch it up a bit.
If we changed the < in the 2nd ...
2
votes
1answer
34 views
Soft question: program result verification
Let's say there's a cloud computing service that allows people to run arbitrary programs and get the results. The idea being that your machine is too slow, and you don't want to overwhelm it. If your ...
1
vote
1answer
35 views
Are consensus (and atomic broadcast) protocols limited by single node's resources?
The main question is the following:
When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, ...
1
vote
0answers
10 views
Where can I find practice for given atom instructions, implement ME
I'm trying to practice for my upcoming distributed systems test. My teacher said that their will be a problem where he'll give us atomic instructions and we're going to have to implement Mutual ...
0
votes
0answers
32 views
Exact difference btw Sequential Consistency vs FIFO Consistency
The both appear same to me. Because in both models order of operations within a process has to be respected. Operation that takes place inter-processes can be mixed just like in sequential consistency....
0
votes
0answers
19 views
Distributed systems, finding N-th lightest weight in graph
I have a complete graph with N vertices, with positive weights assigned to their edges.
Each node knows the weight of its edges.
Each node has a unique ID.
We can send message on each edge, one ...
1
vote
1answer
33 views
Enforcing application layer consensus on top of a distributed consensus protocol
If I understand correctly, the term "consensus" in distributed consensus algorithms means that all the participants ("peers") achieve a common understanding of some data value. Different algorithms ...
0
votes
1answer
71 views
What us difference between distributed computing and workgroup computing?
According to the definition, distributed computing means to distributed a problem among different users while workgroup computing means to work on a problem by different users. So what's the ...
1
vote
0answers
174 views
Distributing Neural Network Training World-Wide Using Blockchain?
I just finished reading a white-paper from a recent AI startup. The company, Deep Brain Chain, wants to distribute neural network training over computers worldwide, using blockchain technology. Here ...
3
votes
1answer
367 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 ...
2
votes
1answer
53 views
FLP Impossiblity Result assumption of $C_1 = e'(C_0)$
FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor ...
