Questions tagged [distributed-systems]

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

130 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
17 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
0answers
34 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 ...
1
vote
1answer
35 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 ...
1
vote
0answers
42 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
83 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 ...
1
vote
0answers
95 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 had ...
1
vote
1answer
96 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
vote
0answers
22 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 ...
1
vote
0answers
71 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 ...
1
vote
0answers
33 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 ...
1
vote
0answers
95 views

How do distributed algorithms for shortest path finding handle negative cycles?

I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
1
vote
0answers
32 views

Why don't RDBMS use a quorum based solution to do failover

For RDBMS viz. MySql, PostgreSql a common solution for scalability and high availability is to run a primary instance as master that is a read-write instance and one or more read replicas. If the ...
1
vote
1answer
429 views

What's the difference between strong consistency and sequential consistency?

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs ... the result of any execution is the same as if the operations of all the processors were executed in some ...
1
vote
0answers
38 views

Tendermint Consensus - Resilient up to 1/3 of Byzantine participants

Tendermint Consensus is resilient for up to 1/3 of Byzantine participants. Question: What actually happens after when the network hits the threshold of byzantine actors? Forking happens? Does ...
1
vote
0answers
57 views

Number of replicas needed for fault tolerance in state machine replication

I am trying to get my head around "State Machine Replication". I understand that it is a way to ensure resilience against failures. I have read that in order to provide fault tolerance against normal ...
1
vote
0answers
139 views

bakery algorithm, switching up the condition

I'm currently studying the Bakery Algorithm. I understand it for what it is but now I want to switch it up a bit. If we changed the < in the 2nd ...
1
vote
0answers
10 views

Where can I find practice for given atom instructions, implement ME

I'm trying to practice for my upcoming distributed systems test. My teacher said that their will be a problem where he'll give us atomic instructions and we're going to have to implement Mutual ...
1
vote
0answers
203 views

Distributing Neural Network Training World-Wide Using Blockchain?

I just finished reading a white-paper from a recent AI startup. The company, Deep Brain Chain, wants to distribute neural network training over computers worldwide, using blockchain technology. Here ...
1
vote
0answers
600 views

How to use version vectors to decide which value to keep?

I am trying to understand how to build an eventually consistent KV store. It's just a learning experiment. Let's only consider one value which stores a fruits list. We have 2 servers, 2 clients, N=2, ...
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
0answers
37 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 ...
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 ...
1
vote
0answers
95 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 $...
1
vote
0answers
164 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 ...
1
vote
0answers
108 views

Processes running in Distributed Systems (Advanced Operating System)

I had a test today, there was a question that was a bit confusing. Anyway I am asking the question, from memory, and explaining what I answered. It would be great if someone could explain if I did ...
1
vote
0answers
529 views

Examples of real world graphs that are too big for a single commodity-type machine

I've been reading on distributed systems for processing on large graphs. The most prominent examples include Pregel (developed by Google) and Apache Giraph. Most of these systems argue their existence ...
1
vote
0answers
48 views

Graph Partition Across Cluster - Minimize Largest Matrix Size

I am writing some code for modeling semi-biologically realistic neural networks, which is to be run/distributed across nodes in a computer cluster. I begin with a very large adjacency matrix (...
1
vote
0answers
115 views

computational and messages complexity equivalence between STP and Leader election

I'm doing a presentation for a distributed systems and networks course. I'm using the book "Design and Analysis of Distributed Algorithms", written by Nicola Santoro. This book contains the proof of ...
1
vote
0answers
90 views

What are the models of distributed storage systems in the literature?

To understand the effectiveness and/or efficiency of a protocol implemented in distributed storage systems, it is often desirable to evaluate it in a quantitative way under a hypothetical model. ...
1
vote
0answers
276 views

Peer discovery: What class of network algorithm prioritises low latency above all else?

I'm trying to flesh out a proposed application model where all peers in a distributed network discover each other in the least possible propagation time. But I'm reached the limit of my knowledge of ...
1
vote
0answers
45 views

Is this protocol suitable for transaction services?

The paper Eventually-Serializable Data Services (PODC'96) presented an eventually-serializable data service. In the abstract, it says: … and generalizes their algorithm (in the related work Lazy ...
0
votes
0answers
19 views

Can blockchain provide any meaningful benefit in more permissioned and less byzantine settings?

Consider as an example the following setting. A set of universities want to keep track of the joint list of students. Ideally, each university will have a "consistent" copy of this list, ...
0
votes
0answers
23 views

How can we prove Karlin and Yao’s probability bound on randomized Byzantine Broadcast protocols?

Can we concretely prove that with 3 nodes (one of which is faulty), a randomized Byzantine broadcast protocol will have a 2/3 probability of success?
0
votes
0answers
13 views

How does organizing several processs on a group makes processes fault tolerant?-process resilience

Has it do with the fact that if f+1 processes are there and f processes fail, still 1 will be able to perform the operation? Or why? I am studying process resilience.(Process resilience=processes can ...
0
votes
0answers
161 views

Some Confusions in Ricart Agrawala second algorithm-token based algorithm for mutual exclusion

Resources that I followed to learn-: http://www.ejbtutorial.com/lectures/petru/lect6-7.frm.pdf https://cis.temple.edu/~wu/teaching/Spring2020_CIS5644_Distributed_Computing/distributed-computing-2020-...
0
votes
0answers
15 views

Is ordering achieved by central server algorithm?

ME3 specifies that the first process be granted access before the second Ordering-: Requests are granted in the order they were requested. Colouris Distributed Systems book-: The reader should ...
0
votes
0answers
15 views

Clock synchronization in distributed system-What is this slide trying to say?

For over an hour I am trying to decode this slide. When each machine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time. Here event output.o ...
0
votes
0answers
27 views

Differences between RPC and RMI

I am studying a notes about RPC vs RMI but I understood not much of it. So asking here. RPC supports procedural programming paradigms this is C based while RMI supports object oriented paradigms so ...
0
votes
0answers
11 views

What are Cloud Infrastructure & Sevices, Distributed Computer Systems, and Internet-of-Things (IOT) Concepts and Applications?

I'm looking for experts to explain these Computer Science subjects that I have to choose in my university. Currently, it seems that IOT and Cloud Infrastructure are quite popular. What are their ...
0
votes
2answers
27 views

Sorting from independently chosen comparisons

I want to sort a list of n items from pairwise comparisons. Each round, I receive k comparisons, one each from ...
0
votes
0answers
38 views

Distributed Algorithm to get an ordered list of nodes in a bipartite graph

Given a weighted bipartite graph with nodes of type A and B, I want to output an (approximately) ordered list of type B nodes as defined by the following heuristic: For each node of type B, sum over ...
0
votes
0answers
20 views

Dominating set in a connected graph

I have a synchronic ring network with $n$ (i.e. the nodes are connected in a ring), and I need a good approximation (factor of 3/2 of the optimal value) for the minimal dominating set. I also need ...
0
votes
0answers
17 views

Partition in a tree shaped distributed network

We are given a synchronic undirected tree shaped network, with $n$ indexed nodes. We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given. We need to ...
0
votes
0answers
27 views

What does it mean that Atomicity is composable?

I'm reading a book from Michel Reynal called Fault-Tolerant Message-Passing Distributed Systems. In chapter five of the book, The Read/Write Register Abstraction, I have a few questions. On page 85, ...
0
votes
0answers
43 views

How to Concurrently Add a Row to a Relational Database

Say I have a relational database and I want to support allowing multiple writers to add create a new row in the same table. How is this implemented? I've read a lot about locks for dealing with ...
0
votes
1answer
55 views

Recommendation for good book or online course on distributed programming

I am a computer science student in his final year on the university with several years of experience in software engineering. I want to take me to the next level in programming web applications. I am ...
0
votes
0answers
18 views

Are there any applications to use a halting decidable system to study security problems in distributed systems?

There's a bounded system S (halting is decidable) that can be used to model reliable asynchronous communication and unreliable asynchronous communication. Are there any applications to use this system ...
0
votes
0answers
14 views

What are overlay & underlaying topologies in DHT?

We are covering Distributed Hash Tables in my "Networks" class and one of the subsections is about the improvements that can be made to increase the performance of the chord. Here, the ...
0
votes
0answers
27 views

Test data for tasks that communicate over network

I am working on a load balancer that schedules tasks that communicate over network. I want to test its performance, but I'm struggling to find test data for it. Currently I try to extract relevant ...
0
votes
0answers
41 views

Designing of reliable multicast algorithm, regarding validity, can you deliver before multicasting

As the title says, if an algorithm delivers $m$ before multicasting $m$, does the validity property still hold? I would argue that it doesn't matter, as the purpose of validity is to ensure that the ...