Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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

Understanding leslie lamport's spacetime diagram with tick lines

I am trying to understand tick lines in Fig 2 on Page 2 of "Time, Clocks, and the Ordering of Events in a Distributed System" paper [1]. Below are 2 things which I did not understand What is the ...
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 ...
0
votes
0answers
33 views

What's a good method to decide wheter distributed or parallel computing?

I've already programed a grammatical evolution on GPU with a very satisfactory result (an improvement on time of about 140% with relative small datasets, expecting better results whith big ones). ...
0
votes
0answers
134 views

Spanning-Tree-Protocol and BFS? (Distributed Computing)

Given is graph with networks and bridges/switches. We know, the root Bridge is the bridge with the minimal Bridge-ID. The connections between every bridge and network is 1. In the lecture slides they ...
1
vote
1answer
588 views

Calculate execution time from linear speedup

Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores? (Assuming Gustafson's law, or in other words, $t(\infty)=0$) My ideas: I ...
5
votes
2answers
4k views

Why is Two-Phase Commit (2PC) blocking?

Can anyone let me know, why 2PC is blocking when the coordinator fails? Is it because the cohorts don't employ timeout concept in 2PC? Good reference: Analysis and Verification of Two-Phase Commit &...
7
votes
1answer
485 views

Impossibility for Byzantine Generals Problem where $n \leq 3m$

Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the ...
3
votes
1answer
89 views

Contamination in Atomic Broadcast in crash stop failure model

I'm reading several papers about different broadcast algorithms. Most of them are designed for crash stop model but they also consider contamination scenarios. For example for a Causal Atomic ...
0
votes
1answer
656 views

What's the difference between a broadcast algorithm and a flooding algorithm?

Both the broadcast algorithm and the flooding algorithm seem exactly the same to me, some sites try to explain the difference but then other sites contradict their statements. At the moment I see both ...
3
votes
1answer
187 views

Is per-record timeline consistency is somehow equivalent to causal consistency?

What I understand about per-record timeline consistency is: For a specific primary key all the insert/update/delete operations should be read in the same order by all replicas. Since all ...
0
votes
0answers
108 views

Distributed MST in $O(n \log \log n)$

I'm facing the following problem: Describe a distributed MST algorithm in time $O(n \log \log n)$ I've managed to think of the following, Run GHS(Gallager, Humblet and Spira) algorithm, till there ...
6
votes
2answers
1k views

How do you compute the time complexity of distributed algorithms?

How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(...
0
votes
0answers
39 views

What are networking technologies to distribute the file faster with storing on more replicas?

Question: Suppose you launch a job on 10,000 machines in your own data centre. The job is slow to start because all the machines are trying to load the same large executable file. Name two networking ...
0
votes
0answers
45 views

What is the probability distribution of arrival times in a distributed system?

I'm going to simulate an asynchronous distributed system. In a distributed system, when a node sends a message, after $\Delta t$ seconds the message reaches to its destination. My Question: What is ...
1
vote
0answers
18 views

In a 'self-stabilized' distributed system, where a fault occurs?

Consider a self-stabilized distributed system based on shared memory and the processor $p_{i}$ be connected to the processor $p_{j}$. Suppose we are going to solve a problem like finding a maximal ...
1
vote
1answer
41 views

New Idea for accessing memory across an inter-network connected system

I have the following idea for a network-based operating system. Suppose we have two computers A and B in a network. If computer B wants to access the memory of computer A, it can access by using the ...
9
votes
2answers
3k views

External consistency vs linearizability

In Spanner, TrueTime & The CAP Theorem, Eric Brewer writes: One subtle thing about Spanner is that it gets serializability from locks, but it gets external consistency (similar to ...
2
votes
2answers
157 views

outside of bitcoin, how does a network negotiate what the next blockchain should be?

There are two problems I see with negotiating the next block chain: which transactions to include in the chain (because consider transaction T which has propagated through exactly 49% of the network ...
3
votes
0answers
46 views

Why does the proposer sends an accept request with the same value it got from the acceptor?

In the second phase of the paxos algorithm, the proposer issues an accept request with the number n and the value v it got from ...
2
votes
0answers
60 views

Distributed consensus feasibility from graph structure

Consider a consensus process in which participants Initially take a position Receive positions only from their neighbors Accept a new position that is a super-majority of neighbors positions. Under ...
5
votes
1answer
260 views

Can I prove that I have x such that f(x) < c without revealing x?

I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) < c for some real-valued function f and some c of Alice's choosing, so she hires Bob ...
1
vote
1answer
175 views

Is potential causality relation equals to set of consistent happens before relations?

In a book dedicated to distributed algorithms, I found the following definition - potential causality diagram is consistent with happens before diagram if potential causality relation between system ...
0
votes
1answer
231 views

Chord algorithm - how to map nodes to keys? [closed]

I'm trying to understand Chord algorithm (for Peer-to-Peer systems) but I can't understand how it maps the documents to the nodes. I have one example where we have: keys with 4 bits 5 active nodes ...
4
votes
2answers
1k views

Where does the FLP impossibility proof depend on allowing a single process failure?

Question I'm reading the FLP impossibility paper. I think I understand the idea of the proof, and I don't have questions about it. However, it seems like the assumption of having at most, a single ...
4
votes
1answer
212 views

Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

Please bear with my unhelpful typesetting. My question is regarding well known FLP paper Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson While ...
4
votes
0answers
475 views

Is there any theory behind GraphQL?

GraphQL is a query language for your API, and a server-side runtime for executing queries by using a type system you define for your data. Source: http://graphql.org/learn/ So GraphQL allows a ...
2
votes
1answer
58 views

Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?

During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these ...
2
votes
1answer
95 views

Classification of technologies used for communication in distributed systems

I am currently writing a State of Art about technologies used for distributed communication (like CORBA for example). I want to structure the document in way that I don't leave any subset of this ...
1
vote
1answer
68 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 ...
1
vote
0answers
35 views

fundamental doubt in definition of routing table

I have some very simple doubt in definition of routing table, and would be thankful if anybody could clarify it. The doubt is that can the routing table of any node, say w, be smaller than the degree ...
2
votes
1answer
80 views

Are there any types of distributed databases which allows untrusted peers, like Blockchain?

Are there any types of distributed databases which allows untrusted peers, like Blockchain? If it exist, can I look its whitepapers and/or implementations?
1
vote
0answers
17 views

Optimal linking in synchronous environment for shortest path tree problem

I am dealing with the Shortest path tree problem in the specific synchronous environment. In the following algorithm, initiator begin the execution calling primitives ...
0
votes
0answers
84 views

When to send a message on distributed systems emulating a FIFO network?

We designed in the lecture of Distributed algorithm an algorithm to emulate a FIFO network as far as an asynchronous network isn't unavoidably FIFO. Yet I have some difficultes to understand the ...
0
votes
0answers
50 views

Reference Request: Distributed Systems Systems

I recently finished Operating System Concepts. As a follow-up for self-teaching, I am looking for a book on distributed systems (not theory). I've found Tanenbaum's text but it has rather poor reviews....
2
votes
0answers
63 views

What is the largest number of Byzantine failures that can be tolerated in an $m$-dimensional hypercube for the consensus problem?

We are given a system with $n$ nodes which have been arranged into the topology of a hypercube of $m$ dimensions. I would like to derive a tight bound on the maximum number of Byzantine failures that ...
1
vote
0answers
84 views

Reduction of flow-shop scheduling to a real-world computing problem

Consider the following well known flow-shop problem: We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$. Each job $J_i$ consists of a set of operations $...
0
votes
0answers
111 views

Distributed Algorithm for Minimum Cost Maximum Matching in General Graphs

What are the fastest distributed algorithms for minimum cost maximum matching in general graphs? I found two papers that talk about approximation algorithms but I want algorithms that solve the ...
4
votes
1answer
835 views

Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?

I've just started reading about theory of distributed systems and am a bit confused. There seem to be two ways of defining a synchronous distributed system and I'm not sure whether they are equivalent....
1
vote
0answers
28 views

Can queueing model capture insights of a system in terms of CPU utilization & service delay? [closed]

After some efforts, I'm really doubtful about the application of that queueing model in analyzing network servers (specially in my case, IP Multimedia Subsystem) as well as predicting the workload. ...
3
votes
1answer
141 views

Are vector clocks useful in centralized systems?

Vectors clocks seem to be a common way to synchronize the partial ordering of events in a distributed, peer-to-peer, system across all clients. Is there any benefit to using them in a centralized ...
1
vote
1answer
83 views

Formal way to model or describe distributed systems architecture

I've been tasked to create the systems architecture for a distributed system. One approach to designing this system is to pick systems architecture patterns, and then evaluate different technologies ...
0
votes
0answers
57 views

Explanation of pilot jobs in distributed/grid computing

I'm reading into grid systems/distributed systems and came across pilot jobs that I can't find a decent explanation for. The wikipedia page is not understandable to me. I know multi-level schemes ...
3
votes
1answer
125 views

Overflow of integer counter in distributed systems

I've just been introduced to Paxos. There is notion of the of value that is incremented each time a new proposal is send. To provide order for proposals, something like time. What happens when this ...
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 ...
-2
votes
1answer
579 views

Both shared-memory and distributed-memory

As you see in the following picture its a shared-memory architecture which has been modeled in a form of complete graph. Why we can consider the following architecture (which is a complete graph) both ...
4
votes
2answers
2k views

Lamport's Bakery algorithm

I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 ...
0
votes
1answer
2k views

Difference between centralized computing and distributed computing using Client-Server

I already understand that Distributed Computing is the breakup of having multiple clients rely on a single source, and having each client utilize other clients for information. But my confusion comes ...
4
votes
3answers
2k views

What is the consensus algorithm that requires an odd number of nodes?

Last week I stood up and gave a talk on the Raft Consensus Algorithm. The first question I got was: Doesn't it need an odd number of nodes? I answered "During leader election, the first node to ...
1
vote
0answers
142 views

Using consensus for atomic commits

I read that consensus algorithms allow you to ensure the atomic commit. That is, in order to save a large amount of data on the disk, as if it is a single object, the article advises a consensus ...
0
votes
2answers
5k views

What is the difference between centralised, decentralised, distributed, fully-distributed?

What is the difference between centralised, decentralised, distributed, fully-distributed, partially-centralised, partially-decentralised system? Which type or topology is the system attached in the ...