Questions tagged [distributed-systems]

Questions about the challenges of solving problems with multiple cooperating but separate agents.

Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

What tree-based barrier is OpenMPI using for their barrier implementation?

I was taking a look at the barrier implementation for OpenMPI and see that they are using a sort of logN tree-based algorithm, but I'm having some trouble grokking the implementation. Seems like a ...
  • 101
1 vote
1 answer
23 views

Reducing BB to SMR and vice versa

It's often said that State Machine Replication and Byzantine broadcast are equivalent (e.g., the abstract of [1]), but it seems only obvious how to reduce SMR to BB. I.e., give BB one can construct an ...
  • 181
0 votes
0 answers
17 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?
1 vote
0 answers
21 views

Can a distributed system designed with logical clocks truly derive a total ordering of events?

I’m reading Leslie Lamport’s white paper, “Time, clocks, and the ordering of events in a distributed system”. His explanation for total ordering has me a bit confused in the following excerpt. I've ...
0 votes
0 answers
25 views

$(d+1)$-coloring $(k, d)$-layered graph using a synchrounous distributed algorithm

Let $G=(V, E)$ be an undirected graph and $m$ be the maximal degree of G. Each vertex v $\in$ V has an initial unique identifier (id) taken from the set {$1,...,n^2$} (when $|V|=n$). Each vertex v $\...
0 votes
0 answers
22 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 +...
2 votes
1 answer
90 views

Information sharing in group

I have a group with n members. These are distributed members. It is basically a group chat. A new member is added to the group and the existing members are informed about this. Now I want the new ...
  • 123
1 vote
0 answers
55 views

For what example would Maekawa's algorithm allow out of timestamp order access to the critical section

For what example would Maekawa's algorithm allow out of timestamp order access to the critical section. It is mentioned that ordering is not satisfied in Maekawa's algorithm. But in what scenario ...
0 votes
2 answers
23 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 ...
3 votes
0 answers
22 views

Proof that state-based (convergent) CRDTs are causally-consistent

Conflict-Free Replicated Datatypes (CRDTs) are a class of distributed data structures where replica states are allowed to temporarily diverge, but will eventually converge (in the absence of network ...
  • 263
0 votes
1 answer
29 views

Split matrix by groups of columns but *capture all combinations of X columns* for some X

Say I have a big matrix, ~50000 rows, ~80000 columns. I want to split it up and solve subproblems on different machines (horizontal scaling). But I need to make sure every column can be combined with ...
0 votes
0 answers
9 views

Equal Network Partitioning in Byzantine Problem with 2 generals

Assuming the typical byzantine setup with generals and lieutenants, communication is binary(attack/retreat) and the graph of communication is complete. Assuming that the maximum number of faulty ...
  • 101
0 votes
1 answer
28 views

Reference request: Time and proofs of a shared past

(Short discaimer: I'm a mathematician by education (category theory, algebraic geometry) and so mostly unaware of how different fields in CS relate to each other. I'd be very happy to just get some ...
0 votes
1 answer
27 views

Where is found the original library of the PBFT consensus algorithm?

In the PBFT paper written by Miguel Castro it has been mentioned: (In Abstract:) "BFT has been implemented as a generic program library with a simple interface." (Also in page 71:) "...
1 vote
2 answers
81 views

Derivation of fraction of time when system has k requests

I was going through Distributed Systems by Maarten van Steen & Andrew S. Tanenbaum. While going through size scalability of systems, I came across this in a note. I want to know the derivation of ...
  • 33
0 votes
1 answer
29 views

How to handle Insert and Delete requests arriving out of order?

Entries need to be stored in a database. There is Insert(entry) RPC, which adds a new entry in a database, and Delete(entry) RPC,...
0 votes
0 answers
49 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 &...
0 votes
1 answer
51 views

How does caching increases scalability in distributed file system?

There are clusters of LAN connected computer systems. California cluster has cached "viral video" at first stage, when client near California requested the file firstly. Now, another client ...
  • 3
1 vote
1 answer
28 views

A lower bound for the makespan of heterogenous fog nodes

Why there is a sigma in the denominator of equation (8) in the picture? suppose we have n tasks and m fog nodes.
  • 25
0 votes
0 answers
24 views

The notion of "simulating an edge" in graph algorithms

I am reading a 1996 paper by Panconesi and Srinivasan :(https://www.sciencedirect.com/science/article/abs/pii/S0196677496900176) on distributed network decomposition. In the analysis of the recurrence ...
  • 371
1 vote
0 answers
22 views

How to select a random node when nodes are untrusted in a distributed network? [closed]

Assume in a distributed network, where the nodes are not trusted and are identified by their public keys, we intend to select one of them in a random process. In such a situation, all of the nodes ...
1 vote
1 answer
57 views

can UTC replace Lamport logical clocks?

if UTC is universal, what drawbacks does it have in using it in a distributed system to coordinate events or use it as a global objective reference clock? isn't it right to just use UTC to timestamp ...
  • 111
3 votes
1 answer
195 views

Lamport Timestamps and Causality

I'm having trouble understanding lamport timestamps in practice and how they guarantee causal ordering. Definitions Lamport defines the "happens before" relationship in his paper. He states ...
  • 133
1 vote
0 answers
27 views

Dot symbol in set-builder expressions in CRDT literature?

In Conflict-free Replicated Data Types: An Overview and other CRDT-related publications by Preguiça's group, a dot symbol often appears without definition. What does it indicate, how standard is it as ...
  • 11
0 votes
1 answer
112 views

Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
0 votes
1 answer
29 views

Difficulty understanding how federation increases cache performance for databases?

I am studying system design for distributed systems and in this page (https://github.com/donnemartin/system-design-primer), one of the following advantages was mentioned for federation for databases ...
  • 125
0 votes
1 answer
36 views

a question related to consensus number of a concurrent object

a) We know that solving consensus in asynchronous distributed systems is impossible. b) Let the consensus number of a concurrent object be cn = 2, which means that two processes can solve consensus ...
1 vote
0 answers
49 views

Is there a distributed streaming algorithm to verify set cover?

I have $k$ sets of similar sizes, that cover a universe $U$. e.g. for $k=3$ and $U = \{1, 2, 3, 4, 5, 6\}$: $S_0 = \{1, 2, 4\}$ $S_1 = \{2, 3, 4\}$ $S_2 = \{4, 5, 6\}$ I have another larger set $C$ ...
  • 123
2 votes
1 answer
92 views

How do distributed joins work in a distributed relational database system?

I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
  • 1,953
1 vote
1 answer
27 views

Term for the total communicated data over a distributed system

I am looking for a publication-friendly term to describe the total quantity of data communicated between nodes of a distributed system, as invoked by some discrete operation. This term would describe ...
0 votes
0 answers
38 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 ...
3 votes
1 answer
36 views

How does a single-node system get Availability in CAP theorem?

I have a question. I read many blogs, websites about CAP theorem. They say that single-node systems are CA, but how can it be "A" if that single node goes down ? Because if it does, the ...
  • 31
1 vote
2 answers
43 views

What are good algorithms for distributed purchasing?

I'm looking for some algorithms/patterns to solve a distributed systems problem. Lets say I have created a trading platform buying stock (I haven't), and I have a distributed system of 50 nodes that ...
  • 13
0 votes
1 answer
18 views

Does pattern matching require having the data on one machine?

Is it possible to use pattern matching algorithms such as FP-Trees and others on data that resides in multiple machines? Basically when doing pattern matching do you have to have all your data on the ...
0 votes
0 answers
51 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
20 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 ...
2 votes
0 answers
52 views

Is this simple Asynchronous Byzantine Consensus Protocol correct?

I'm trying to solve a problem that may arise in a system I am concerned with. It will be uncommon in practice, so I am more concerned about simplicity and correctness than performance. I have N ...
1 vote
0 answers
48 views

Modern standard texts on distributed systems

I'm starting a job soon that involves a large number of disciplines interacting at once. I'm knowledgeable in most of these areas; at least enough that when I don't know something I know how to look ...
  • 3,758
1 vote
0 answers
51 views

Can decentralised systems mitigate 51% attacks by design?

Can you make decentralised systems, e.g. cryptocurrencies or serverless games, that aren't susceptible to 51% attacks by design? (Rather than, as I've seen proposed, external solutions like fining ...
1 vote
0 answers
35 views

Bully Algorithm Timeout After Receiving a Response from a Higher Process

Im specifically referring to the bully algorithm for synchronous systems, described in [Garcia-Molina 1982]. In it, the timeout for failure detection is concretely defined as the sum of the round trip ...
2 votes
0 answers
19 views

Minimum number of registers for mutual exclusion

I was reading distributed algorithms (by Nancy lynch) and there is a part that I would kindly like to get a simpler explanation for. I know the book mentioned no algorithm can solve mutual exclusion ...
0 votes
0 answers
25 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, ...
  • 121
3 votes
2 answers
79 views

Proof in the "Reaching Agreement in the Presence of Faults"

I am reading the "Reaching Agreement in the Presence of Faults", M. Pease et al and trying to understand their proof for the $n \geq 3m+1$ case. In the induction step $m \gt 0$ it says the ...
  • 31
0 votes
1 answer
122 views

What is the meaning of the pipe symbol here?

I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that ...
-1 votes
1 answer
36 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 ...
1 vote
1 answer
177 views

Invariant vs Assertion vs lemma

I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate ...
1 vote
1 answer
848 views

How is this example sequentially consistent but not linearizable?

Background information that I know(But not understand with examples, I will be glad if you could explain it to me with examples) A replicated service is said to be linearizable if for any executin ...
user avatar
1 vote
0 answers
13 views

Distributed Graph Consensus to fit a distribution?

$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance. The objective is for ...
  • 502
1 vote
0 answers
132 views

How is this example related to Lamport clock theory? I can't relate algorithm example with the algorithm theory. Share some insights please [closed]

I have asked 1 type of question but I have asked that in many questions. So bear with me. My question is about 1 topic, I just didn't find it right to create separate questions for each of these ...
-1 votes
1 answer
61 views

If primary server's UTC source fails, how will synchronization be possible in NTP(network time protocol)?

If a primary server's UTC source fails, then it can become a stratum 2 secondary server. If a secondary server's normal source of synchronization fails or becomes unreachable, then it may synchronize ...

1
2 3 4 5
8