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
0answers
11 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 ...
0
votes
1answer
16 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 ...
2
votes
2answers
1k views

What does atomicity mean in distributed systems?

In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem? Does atomicity have a different meaning in this context?
1
vote
0answers
15 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
24 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 ...
3
votes
1answer
122 views

What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?

After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages ...
3
votes
1answer
658 views

What guarantees Paxos to converge (terminate)? (i.e. not run forever without a consensus)

I was studying Paxos from: http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf and was wondering, what guarantees Paxos to converge and not run forever without a consensus/...
1
vote
0answers
56 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 ...
0
votes
1answer
38 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 ...
0
votes
1answer
220 views

What is a genuine atomic multicast?

What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?
1
vote
1answer
53 views

Is There An Established Way To Send Code Over a Network?

Let's say I have two computers on a network. I want to write code in some language on machine A, send the code in an efficient way over a network, and run the code on machine B. It seems to me that ...
0
votes
0answers
10 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
15 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 ...
1
vote
1answer
21 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 ...
1
vote
0answers
17 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. ...
5
votes
1answer
504 views

blockchain database - why so redundant

I've become interested in blockchain databases. Everywhere I've read it said that each user has to have his/her own copy of database. Why can't distributed blockchain database be 'distributed' to ...
0
votes
0answers
9 views

Time-slice Equalizing Algorithm

I have a requirement for which I am trying to write an algorithm and struggling a bit conceptually with. This seems like it should be a common-ish type problem so I imagine there is a name/standard ...
0
votes
0answers
17 views

Consistency CAP vs ACID

I understand that the consistency property specifies what values can be read, depending on what has been written before. For instance, if we consider a simple abstract read/write service. It enjoys ...
1
vote
1answer
185 views

How to compare distributed systems and big data

Are there scientific papers that compare distributed systems and big data processing systems? Big data processing systems can be batch processing systems or streaming big data processing systems. A ...
1
vote
1answer
66 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
10 views

Graph with arboricity a, all verteces are marked active

So I came across this problem that I would like help solving/explaining: We have a graph with arboricity a (can be partitioned to a min of a trees). We run the following algorithm on the graph: - All ...
3
votes
1answer
197 views

Is it possible to write a wait free leader election algorithm?

I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously. Finally I want to know how to derive the consensus number of this algorithm. ...
1
vote
2answers
99 views

Are consensus (and atomic broadcast) protocols limited by single node's resources?

The main question is the following: When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, ...
2
votes
2answers
110 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 ...
0
votes
0answers
17 views

Can't understand this example of convergecast addition from a book

In the book Distributed Computing: A Locality-Sensitive Approach by David Peleg, in chapter 3, Broadcast and convergecast, in section 3.4.2 Global function computation, examples are given for global ...
0
votes
1answer
213 views

sequential consistency is not composable

I am studying for my exam in Distributed Systems course. And i have one question that i do not really understand. This is the question: ...
0
votes
0answers
22 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
18 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 ...
13
votes
3answers
3k views

What is the origin of the client server model?

I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?
0
votes
0answers
13 views

Questions while I'm making distributed key-value store

I'm CS student. I'm currently trying to make distributed key-value store. Since I'm new to distributed system concept. I'm struggling with sort of concrete implementation and methodology to apply ...
1
vote
0answers
65 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
11 views

How to detect a consensus is BFT or not?

Can we divide consensus algorithms into BFT (Byzantine Fault Tolerant) and non-BFT ? If so, How to detect a consensus is BFT or non-BFT ? Is there any non-BFT consensus algorithm example ?
0
votes
0answers
25 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 ...
1
vote
1answer
496 views

Difference between Lamport timestamps and Vector clocks

Lamport timestamps and vector clocks sound like almost the same thing. Both are used to determine the order of events in a distributed system. What are their key differences?
2
votes
0answers
27 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
19 views

What is the relationship between Consistency Models and Consensus Algorithms?

I know that: Each replication technique should follow a consistency model. A consistency model defines a set of rules for the order of the write and read operations. In some replication techniques ...
3
votes
1answer
134 views

What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?

Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle). It ...
0
votes
0answers
45 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
0answers
9 views

How to make use of opponent policy on designing ours in multi-agent learning

I'm currently working on a multi-agent reinforcement learning. The setting is a cooperative multi-agent system with a stationary assumption on the opponent policy. Suppose I have the model of the ...
0
votes
0answers
16 views

Distributed selection (window) algorithm

For n records distributed amongst m processes/nodes (no shared memory) I'd like to accomplish the following for some given ranking criteria find the rth item. find the rth to r+cth items for some ...
3
votes
2answers
159 views

Paxos made simple — two details

I'm missing two details from Paxos made easy P1. An acceptor must accept the first proposal that it receives. What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon ...
2
votes
1answer
52 views

Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
1
vote
0answers
25 views

Why in the Map Reduce Implementation, why not stream the records to the reducer (via TCP) as they are being produced by the mappers?

In the Map-Reduce implementation, the reducers start when all mappers finish their jobs. Why don't we stream the records from mappers to reducers while they are being processed instead? I think there ...
24
votes
7answers
13k views

Start learning about Theory of Distributed Systems?

What's the best way that anyone can do to have a good introduction to the theory of distributed system, any books or references, and topics should be covered first and requirements to start learning ...
1
vote
1answer
66 views

What mathmatical model shall be used for describing P2P processes interaction?

I am creating a distributed service system. It runs in the cloud on heterogeneous hardware. I am using C# .NET for business logic and C++ for different physics\chemical calculations. Having three ...
2
votes
0answers
38 views

Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= nodes). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
0
votes
0answers
20 views

Need a layman's example of Linearizable Consistency model

As far as I understand, Linearizable Consistency model is a Data-centric and Strong consistency model. Data-centric means: - All clients experience the consistency - All clients access the same ...
0
votes
0answers
40 views

Should I use lamport logical clock or vector clock or something else?

simplified use case: I have 3 nodes where each node sends a message to the other two always(so a message won't be sent from one to another node. It would always be sent to two other nodes) and every ...
4
votes
1answer
910 views

What is the standard way to choose a new leader in Multi-Paxos?

If you are unfamiliar with multi-Paxos or paxos, the following link might be a good refresher on it: http://amberonrails.com/paxosmulti-paxos-algorithm/ or the paper by Leslie Lamport: http://...
61
votes
6answers
65k views

Distributed vs parallel computing

I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty ...