Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
322
questions
0
votes
0answers
13 views
Why is shared register's consensus number 1?
I'm trying to understand the consensus number concept. It is trivially clear that a shared register doesn't create any problem when there is only one thread using it. By why does its consensus number ...
2
votes
1answer
24 views
Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric
I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The ...
2
votes
0answers
38 views
Why is the 'Integrity' property required in consensus protocols?
Formally a consensus protocol must satisfy the following three properties:
Termination
Eventually, every correct process decides some value.
Integrity
If all the correct processes proposed the same ...
3
votes
1answer
26 views
Randomly assign n elements to n agents such that each agent only knows its own element
Problem
I'm working on an app that involves shuffling and distributing playing cards to players. As a challenge, I tried to solve this problem in a way that doesn't require a trusted intermediary.
In ...
1
vote
1answer
81 views
Distributed predicate computation on event stream
My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work.
I'm working on a program that computes a predicate value (true or false) for ...
0
votes
0answers
8 views
Why chord protocol (peer - to - peer) maintains a finger table instead of entire membership list (using SWIM)?
Chord uses finger table for querying and it takes O(log(N)) to get the result. But why not maintain the entire membership list and get result in O(1) ?
1
vote
0answers
19 views
Number of referee nodes required in distributed leader election algorithm
I know the reason as to why $O(\sqrt{n\log n})$ referee nodes are required. What I don't understand is how to arrive at that value, when I have $7\log n$ candidate nodes. Please forgive me if this is ...
1
vote
1answer
21 views
Confused between 2 phase locking and 2 phase commit
I understand that both algorithms are very different, but what I don't understand is whether they achieve the same thing in the end. 2PC is for atomic commits and 2PL is for serializable isolation. ...
4
votes
0answers
30 views
What are some advanced background topics I'll need for distributed systems and networks research?
I am a new graduate student in Computer Science who would like to be able to read and understand modern and new distributed systems research papers. My current background / courses and understanding ...
0
votes
0answers
5 views
What is the current definition for HPC systems - do they include both GPUs and MIMD Supercomputers?
I have seen several definitions across the internet and this question still bugs me.
2
votes
0answers
20 views
Finding the timestamps of processes implementing Lamport's clocks
I have been asked this question, but don't know how to go about answering it.
Three process, which are implementing Lamport's clocks, are running and a lot of events are taking, place including some ...
0
votes
0answers
14 views
Count nodes with more than 3 neighbours in distributed computing, initiating by one site
I have an algorithm that visit all the nodes on a graph in distributed computing , the initiator is one site only , I want to change it so that the initiator can in the end of the execution know the ...
0
votes
0answers
14 views
What are the advantages of NHSX centralised protocol for Contact Tracing?
Apple and Google have published a protocol for privacy-presercing contact tracing - https://www.apple.com/covid19/contacttracing/
They use a decentralised approach where the 'matching' process take ...
0
votes
0answers
7 views
A single Paxos instance deciding on different values
I have recently been taught about the Paxos consensus protocol in my university's distributed systems course. There is a particular case that I find troubling:
Suppose there are two proposers P1 and ...
0
votes
0answers
12 views
Request committed by only some non-faulty nodes in PBFT
I have recently learned about the protocol described in the paper titled "Practical Byzantine Fault Tolerance", as part of my university course on distributed systems. There was one example ...
1
vote
1answer
50 views
Why is two-phase commit better than naive master-slave replication?
In the context of a distributed database, I'm trying to understand why 2PC (as described in e.g. https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/L6-2pc.pdf) is better than the ...
0
votes
0answers
24 views
Optimize Max-flood algorithms bounds
In distributed algorithms, The Max Flood algorithms finds the leader in a network of processes In O(diam) time and with |E|*diam ...
1
vote
1answer
31 views
Why is a threshold determined for Byzantine Fault Tolerance of an “Asynchronous” network? (where it cannot tolerate even one faulty node)
In following answer (LINK: https://bitcoin.stackexchange.com/a/58908/41513), it has been shown that for Asynchronous Byzantine Agreement:
"we cannot tolerate 1/3 or more of the nodes being ...
0
votes
0answers
38 views
Doesn't Linearizability implies Serializability?
Serializability is a concurrency scheme where the concurrent transaction is equivalent to one that executes the transactions serially.
In Linearizability,
Once write completes, all later reads should ...
1
vote
0answers
17 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 ...
0
votes
0answers
8 views
Environmental/Economical benefits of not transmitting parts of a video?
Are there any potential environmental och economical benefits (in terms of infrastructure) derived from not transmitting video packets unless absolutely necessary or requested by the client for Media-...
1
vote
0answers
29 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 ...
0
votes
1answer
106 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
72 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 ...
0
votes
0answers
24 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
155 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
114 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
34 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
16 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
46 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
52 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
27 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
17 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
30 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
50 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 ...
1
vote
1answer
26 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
74 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 ...
0
votes
0answers
13 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
26 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 ...
2
votes
1answer
39 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
1answer
70 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
45 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 ...
2
votes
2answers
122 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 ...
1
vote
1answer
86 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
36 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
21 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 ...
1
vote
0answers
70 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
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
33 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
51 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)
