# Questions tagged [distributed-systems]

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

398 questions
Filter by
Sorted by
Tagged with
13 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 ...
• 295
1 vote
15 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 ...
1 vote
52 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 (...
32 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:/...
• 101
35 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$ ...
• 295
26 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 ...
• 227
28 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 ...
• 101
21 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 ...
• 178
14 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
24 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 ...
• 191
24 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
23 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 ...
25 views

• 123
101 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 ...
• 2,103
1 vote
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 ...
• 111
39 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
39 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
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
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 ...
• 251
55 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
21 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 ...
54 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 ...
• 121
1 vote
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,760
1 vote
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 ...
• 151
1 vote
39 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 ...
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 ...
• 310