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

Doesn't Linearizability implies Serializability?

Serializability is a concurrency scheme where the concurrent transaction is equivalent to one that executes the transactions serially. In Linearizability, Once write completes, all later reads should ...
1
vote
0answers
11 views

Arbitrary fault abstraction in 'Reliable and Secure Distributed Programming'

In the book by Cachin, Guerraoui, Rodrigues they discuss an arbitrary fault abstraction. It seems to me that this abstraction does not include crashes in its behavior. I think this because they ...
1
vote
2answers
75 views

To reach k set consensus (k=2)

If I can use FIFO queue and read/write registers, can I reach wait free 2 set consensus if I have 3 processes? I thought is I can, but I saw a conclusion from text book says "we cannot achieve 2 set ...
0
votes
1answer
63 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
332 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?
4
votes
0answers
67 views

What distributed consensus algorithms don't rely on a time source?

I'm looking for information about distributed consensus algorithms that: maintain a consistent transaction log across all healthy nodes have similar high-availability properties to Paxos (i.e. not ...
1
vote
1answer
38 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 ...
0
votes
0answers
8 views

Environmental/Economical benefits of not transmitting parts of a video?

Are there any potential environmental och economical benefits (in terms of infrastructure) derived from not transmitting video packets unless absolutely necessary or requested by the client for Media-...
1
vote
0answers
23 views

What are the correlation between Actor model and Reactive Programming

Could anyone explain the difference/relation between the Actor model and Reactive programming? It seems that they are located at different levels of abstraction - one can design the interaction ...
0
votes
1answer
50 views

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used ...
0
votes
0answers
19 views

Consensus without majority

I am new to distributed computing but after a quick look at Paxos and Raft it is clear that for those algorithms to work majority of the servers should be up and running. So is it fundamental to ...
1
vote
1answer
19 views

Implementing reliable pairwise average in distributed systems

Consider an asynchronous and unreliable distributed system. Each node has a value. Suppose that p and q are two neighbor nodes of the system (p_val and q_val are the values of p and q respectively). p ...
2
votes
1answer
293 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 ...
-3
votes
1answer
111 views

What is the difference between masking and tolerating failures?

Distributed Systems 5ed by Coulouris says on p21-22 1.5.5 Failure handling Detecting failures: Some failures can be detected. For example, checksums can be used to detect corrupted data in a ...
1
vote
1answer
77 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 ...
-1
votes
1answer
33 views

Do arbitrary/Byzantine failures include omission failures and timing failures?

Distributed Systems 5ed by Coulouris says on p68 2.4.2 Failure Models Omission Failures ... Arbitrary Failures The term arbitrary or Byzantine failure is used to describe the worst ...
0
votes
1answer
24 views

How to convert a centralized algorithm to a distributed algorithm?

Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis?
0
votes
0answers
14 views

Ideal time complexity in analysis of distributed protocol

I need some explanation about the definition of ideal time complexity. My textbook says: The ideal execution delay or ideal time complexity, T: the execution delay experienced under the ...
1
vote
1answer
41 views

How do I use message passing to find the maximum of all values in a grid?

I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly ...
6
votes
3answers
403 views

Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link ...
2
votes
0answers
40 views

Leader election in synchronous ring with unreliable communication channels

As a part of my Distributed Systems course I am required to provide an algorithm that is able to elect a leader in a synchronous bidirectional ring, where every message that is sent may be lost (lets ...
0
votes
1answer
23 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 ...
0
votes
0answers
17 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 ...
2
votes
2answers
2k 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
20 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
36 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
133 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 ...
4
votes
1answer
714 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
64 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 ...
1
vote
1answer
57 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
12 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
21 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
0answers
26 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
511 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
13 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
20 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 ...
0
votes
0answers
12 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
209 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
110 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
113 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
18 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
245 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
29 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
19 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
30 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
67 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
12 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
26 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 ...
2
votes
1answer
1k 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?

1 2 3 4 5 7