Skip to main content

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
13 views

Datastore supporting TTL with range queries

We have a data access pattern in which we need to get users added in the time range say timestamp-1 to timestamp-2 and we don't want to keep older data say max 1 day, so DB should have an inbuilt ...
tusharRawat's user avatar
2 votes
2 answers
55 views

A pedagogic review on the advantage/drewbacks of distributed computing

I need to understand the motivations behind distributed computing, namely the fact to perform a computation by making physically separated computer, connected by communication links, work together. I ...
StarBuck's user avatar
  • 137
0 votes
0 answers
21 views

Optimal way to send data across an unknown network

The problem goes as follows: Given a graph G with a set of Vertices V, each having some capacity u, and edges between them E (not fully-connected) associated with some cost c (cost to send a unit of ...
EnderNicky's user avatar
1 vote
1 answer
89 views

What happens when two different nodes have the same Lamport clock ID

With Lamport clocks, each node keeps its own counter. Before sending a message, a node increments its counter by one: LC(A)=LC(A)+1, and sends ...
A. Darwin's user avatar
  • 123
1 vote
1 answer
32 views

Topological/metric space formed by behaviors of distributed system: Safety and Liveness

In the book A Science of Concurrent Programs Leslie Lamport describes alternative way how to look at safety and liveness properties in distributed algorithms. A.5 Another Way to Look at Safety and ...
Andreo's user avatar
  • 113
0 votes
0 answers
18 views

How can Amazon Aurora gain higher read-only throughput?

I read the Amazon Aurora paper and in the performance result section (i.e. 6.1.1), it says The results are shown in Figure 7 and Figure 6, and measure the performance in terms of write and read ...
hikky36's user avatar
  • 101
1 vote
0 answers
25 views

Why is Bully algorithm in leader election considered synchronous?

The original paper of Bully algorithm [1] does not make any assumption of a synchronous processing. But I see few lectures explicitly call it suitable for synchronous processing. I am not sure why do ...
KRG's user avatar
  • 11
0 votes
0 answers
11 views

In SSTables, why is it possible to group records and compress them?

I am currently reading 'Designing Data Intensive Applications' by Kleppman. In the SSTables and LSM Trees section, it is mentioned that one of the advantage of SSTables is: "Since read requests ...
Udeshya D.'s user avatar
1 vote
1 answer
60 views

Strategy of gradually integrating more complex distributed system into start up company

My 1st question ever on stackexchange, please be nice to me if it's too naive :) I read the map reduce paper and i discover distributed system is expensive. As an example in the paper, roughly ...
Effy's user avatar
  • 11
0 votes
0 answers
27 views

Can we make Paxos live with a failure detector in W?

I was studying Paxos and Failure Detectors, and it was asked whether a failure detector W could be used to make Paxos live, but I can't figure it out. Any suggestions?
Eihort's user avatar
  • 1
4 votes
0 answers
41 views

Prior or subsequent art for Microsoft COM’s “causality IDs”

Microsoft COM, in its object RPC part, had a peculiar mechanism that could be used to prohibit concurrent calls to the same object (or another object serviced by the same event loop) but permit ...
Alex Shpilkin's user avatar
3 votes
0 answers
30 views

Why is there no self-stabilizing determinsitic algorithm for vertex coloring in general graphs?

This question considers the design of a deterministic self-stabilizing algorithm for vertex coloring in uniform anonymous networks. Uniform anonymous networks do not have distinguished nodes and all ...
NoName123's user avatar
  • 171
1 vote
2 answers
56 views

What is the proof in FLP for statement that "clique with majority of processes exist" if majority of the processes live?

The FLP paper provides proof in section "4. Initially Dead Processes" that consensus is possible if majority of processes live and no process dies during the consensus protocol. The proof ...
Ferenc Janosi's user avatar
0 votes
0 answers
21 views

Algorithm to balance candies among students

Let's say N students S1, S2, ... SN with their respective candies count c1, c2,... cN The ask is to distribute the candies (...
Novice User's user avatar
0 votes
0 answers
20 views

Are there free/paid DISTRIBUTED solvers for a large system pf linear equations?

I've been doings some research into distributed solutions for a large system of linear equations (reading papers such as Wang et al.'s "Solving a system of linear equations: From centralized to ...
Karla's user avatar
  • 1
0 votes
0 answers
50 views

Algorithm for leader election in synchronous ring with a known network size $n$ with phases of length $\frac{n}{m}$

Consider the following leader election algorithm election of a synchronous ring with a known network size $n$ (simultaneous wakeup and uni-directional communication): The leader is the node with the ...
Gabi G's user avatar
  • 325
2 votes
0 answers
92 views

Finding a connected subset of edges with minimal sum of weights for a distributed network

Let there be $n$ processes in a general connected network with no leader such that each process has a distinct UID. Each edge has a weight , with weights being positive or negative. Assume that each ...
Danny Blozrov's user avatar
1 vote
0 answers
27 views

Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds

Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system: 1: Assume that initially the nodes have IDs of size $\log(n)$ bits 2: The root is ...
Gabi G's user avatar
  • 325
1 vote
0 answers
65 views

Networks and data flow - graph algorithms for propagating updates from nodes correctly

Suppose I have an acyclic directed graph of Nodes which subscribe to Events. When an Event callback is activated for some Node, the Node's internal update() method is called. Then, because the Node ...
Mike Battaglia's user avatar
1 vote
1 answer
224 views

How does non-DMA transfers really work?

I recently discussed DMA and non-DMA with my OS professor. Here is my current understanding: disk controller has its own CPU, maybe own ISA, tiny program that simply handles reading from the disk (...
user129393192's user avatar
0 votes
1 answer
50 views

Ticket Dispenser algorithm and the size of the Ticket array

The following is a ticket Dispenser Mechanism, it's from the article: "Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion By Robert Danek and Wojciech Golab" http:/...
RT.'s user avatar
  • 101
0 votes
1 answer
37 views

Universal lower bound of the multi message problem

The multi message problem is: Let there be an undirected graph $G = (V,E)$ with $n$ vertices, and let $r \in G$. The algorithm sends a message $M_i$ of size $\Omega(\log(n))$ to each vertex $v_i$ ...
Gabi G's user avatar
  • 325
3 votes
1 answer
32 views

Logics for multi-agent and distributed systems and algorithms

The various temporal logics are particularly suitable for the specification and verification of concurrent computer programs. Are there logics that are particularly suitable for the specification and ...
Evan Aad's user avatar
  • 237
0 votes
0 answers
34 views

Fault-Tolerant Distributed Work Sharing

I have a network of 1,000 computers that are sharing processing jobs. There are a few constraints: Each computer has a maximum ratio of jobs it can perform Can be higher than an equal share ...
Origin's user avatar
  • 101
0 votes
2 answers
51 views

How to interpret the concept of adjacent initial states in the FLP impossibility paper?

Link: https://dl.acm.org/doi/pdf/10.1145/3149.214121 In the proof for Lemma 2, the authors define two initial states to be adjacent if the only difference between them is the value in the input ...
MuchToLearn's user avatar
1 vote
1 answer
29 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 ...
qweruiop's user avatar
  • 201
0 votes
0 answers
35 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?
Tarun Gupta's user avatar
1 vote
0 answers
44 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 ...
Shawn Armstrong's user avatar
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 +...
Reem Aljunaid's user avatar
2 votes
1 answer
93 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 ...
Kobski's user avatar
  • 123
1 vote
0 answers
90 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 ...
sd22gg44's user avatar
0 votes
2 answers
42 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 ...
DarkArtistry's user avatar
3 votes
0 answers
38 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 ...
abeln's user avatar
  • 263
0 votes
1 answer
33 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 ...
Alexander Mills's user avatar
0 votes
1 answer
30 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 ...
Gerrit Begher's user avatar
0 votes
1 answer
52 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:) "...
Questioner's user avatar
1 vote
2 answers
192 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 ...
Dhruv's user avatar
  • 133
0 votes
1 answer
60 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,...
mercury0114's user avatar
0 votes
0 answers
74 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 &...
Questioner's user avatar
0 votes
1 answer
54 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 ...
altoid's user avatar
  • 3
1 vote
1 answer
32 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.
learner's user avatar
  • 25
1 vote
0 answers
25 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 ...
Questioner's user avatar
1 vote
1 answer
93 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 ...
ezio's user avatar
  • 111
3 votes
1 answer
402 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 ...
RSHAP's user avatar
  • 133
1 vote
0 answers
35 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 ...
aas's user avatar
  • 11
0 votes
1 answer
224 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+...
scroobius's user avatar
0 votes
1 answer
36 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 ...
Henry Zhu's user avatar
  • 125
0 votes
1 answer
49 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 ...
user147703's user avatar
1 vote
0 answers
50 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$ ...
zetaprime's user avatar
  • 123
2 votes
1 answer
202 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 ...
Lance's user avatar
  • 2,243

1
2 3 4 5
9