Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
136
questions with no upvoted or accepted answers
0
votes
0
answers
34
views
Difference between Distributed File System, Cluster File System and Parallel File System
On the internet, I am unable to find concrete definitions of these three types of file-systems. Can someone clearly explain the difference between these?
0
votes
0
answers
26
views
Analyzing Parallel Matching Algorithm - Why it takes O(n+m) time and work?
Using the algorithm provided by this paper, they said that:
The algorithm defines a single phase of the local max algorithm. Each step of the phase takes at most O(log(m + n)) = O(logn) time and O(n +...
0
votes
2
answers
40
views
Chord Ring with limited table size of 3
In the normal case of a chord ring the big O notation of the look up is O(logn) because of long haul pointers of the Finger Table (or Routing Table).
In this question what if the Finger Table has a ...
- 111
0
votes
0
answers
73
views
How does PBFT tolerate Byzantine Leaders?
It is said that PBFT (or Practical Byzantine Fault Tolerance consensus) is Byzantine fault tolerant (unlike Paxos or Raft that are only Crash fault tolerant.)
Based on this answer : LINK , in PBFT &...
- 145
0
votes
0
answers
41
views
Why can't we solve the consensus problem by just enforcing a new leader?
I am going through this lecture series by Martin Kleppman. In this video at around 1:25, he says you can manually configure the distributed nodes to chose a leader.
If that's the case can't we just ...
- 101
0
votes
0
answers
83
views
Does DHT (Distributed Hash Table) allow to list ALL (not only nearest) nodes?
As I know any local DHT keeps only some of nodes - if the network is small/very small then all nodes, otherwise only some of them (nearest?).
So, when I checked different Golang implementations of DHT ...
- 101
0
votes
0
answers
24
views
Resources to self-study counting/sorting networks
I am reading The Art of Multiprocessor Programming. I was able to grasp almost everything up to Counting Networks in chapter 12 - Counting Sorting and Distributed Coordination. However I am having ...
0
votes
0
answers
34
views
Can blockchain provide any meaningful benefit in more permissioned and less byzantine settings?
Consider as an example the following setting.
A set of universities want to keep track of the joint list of students. Ideally, each university will have a "consistent" copy of this list, ...
- 131
0
votes
0
answers
81
views
Distributed Algorithm to get an ordered list of nodes in a bipartite graph
Given a weighted bipartite graph with nodes of type A and B, I want to output an (approximately) ordered list of type B nodes as defined by the following heuristic:
For each node of type B, sum over ...
- 101
0
votes
0
answers
18
views
Partition in a tree shaped distributed network
We are given a synchronic undirected tree shaped network, with $n$ indexed nodes.
We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given.
We need to ...
- 33
0
votes
1
answer
149
views
Recommendation for good book or online course on distributed programming
I am a computer science student in his final year on the university with several years of experience in software engineering. I want to take me to the next level in programming web applications.
I am ...
- 31
0
votes
0
answers
28
views
Test data for tasks that communicate over network
I am working on a load balancer that schedules tasks that communicate over network. I want to test its performance, but I'm struggling to find test data for it. Currently I try to extract relevant ...
- 1
0
votes
0
answers
62
views
Designing of reliable multicast algorithm, regarding validity, can you deliver before multicasting
As the title says, if an algorithm delivers $m$ before multicasting $m$, does the validity property still hold? I would argue that it doesn't matter, as the purpose of validity is to ensure that the ...
0
votes
1
answer
299
views
Correctness of Linearizability vs Sequential consistency in replication
I'm currently studying Sequential consistency vs linearizability:
I know that SC has to be consistent with the order of how the individual client issued them, and for linearizability, it's with the ...
- 123
0
votes
0
answers
19
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 ...
- 101
0
votes
0
answers
19
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
0
votes
0
answers
29
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 ...
0
votes
0
answers
219
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 ...
- 101
0
votes
0
answers
115
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
0
answers
57
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 ...
- 156
0
votes
0
answers
110
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.
...
- 157
0
votes
0
answers
41
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 ...
- 111
0
votes
0
answers
145
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 ...
- 742
0
votes
0
answers
53
views
Name for pattern of addressing items by sequence-of-creation
I'm looking for the name of a particular pattern, and/or resources (articles) on its usage.
The context of the pattern is a journalling system to operate on some collection, as in the example given ...
0
votes
0
answers
28
views
Retroactively ordering actors' concurrent activity on disjoint sections of a data-structure
Hi! I'm new here, a terrible computer-scientist, and have no idea what I'm doing; I'm more expecting / hoping for links to research on algorithms or data-structures that contribute to problems like ...
- 101
0
votes
0
answers
142
views
Understanding leslie lamport's spacetime diagram with tick lines
I am trying to understand tick lines in Fig 2 on Page 2 of "Time, Clocks, and the
Ordering of Events in a Distributed System" paper [1]. Below are 2 things which I did not understand
What is the ...
- 101
0
votes
0
answers
43
views
What's a good method to decide wheter distributed or parallel computing?
I've already programed a grammatical evolution on GPU with a very satisfactory result (an improvement on time of about 140% with relative small datasets, expecting better results whith big ones). ...
- 221
0
votes
0
answers
207
views
Spanning-Tree-Protocol and BFS? (Distributed Computing)
Given is graph with networks and bridges/switches. We know, the root
Bridge is the bridge with the minimal Bridge-ID. The connections between every bridge and network is 1.
In the lecture slides they ...
- 219
0
votes
0
answers
237
views
Distributed MST in $O(n \log \log n)$
I'm facing the following problem:
Describe a distributed MST algorithm in time $O(n \log \log n)$
I've managed to think of the following,
Run GHS(Gallager, Humblet and Spira) algorithm, till there ...
0
votes
0
answers
43
views
What are networking technologies to distribute the file faster with storing on more replicas?
Question: Suppose you launch a job on 10,000 machines in your own data centre. The job is slow to start because all the machines are trying to load the same large executable file. Name two networking ...
0
votes
0
answers
63
views
What is the probability distribution of arrival times in a distributed system?
I'm going to simulate an asynchronous distributed system. In a distributed system, when a node sends a message, after $\Delta t$ seconds the message reaches to its destination.
My Question: What is ...
- 271
0
votes
0
answers
113
views
When to send a message on distributed systems emulating a FIFO network?
We designed in the lecture of Distributed algorithm an algorithm to emulate a FIFO network as far as an asynchronous network isn't unavoidably FIFO.
Yet I have some difficultes to understand the ...
0
votes
0
answers
60
views
Reference Request: Distributed Systems Systems
I recently finished Operating System Concepts. As a follow-up for self-teaching, I am looking for a book on distributed systems (not theory). I've found Tanenbaum's text but it has rather poor reviews....
- 2,230
0
votes
0
answers
123
views
Distributed Algorithm for Minimum Cost Maximum Matching in General Graphs
What are the fastest distributed algorithms for minimum cost maximum matching in general graphs?
I found two papers that talk about approximation algorithms but I want algorithms that solve the ...
- 1,198
0
votes
0
answers
78
views
Explanation of pilot jobs in distributed/grid computing
I'm reading into grid systems/distributed systems and came across pilot jobs that I can't find a decent explanation for. The wikipedia page is not understandable to me.
I know multi-level schemes ...
- 9
-1
votes
1
answer
43
views
How does clients observe different replicas and stale data even if the replicas include same set of updates?
I am studying about gossip architecture.
This is gossip architecture-:
Gossip architecture provides 2 guarentees-:
1)Each client gets consistent service over time(meaning even if clients use ...
