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

How to reconcile the different definitions of asynchrony?

There are 3 definitions of asynchrony that I know of: In event-based programming, asynchrony refers to the execution of tasks in a non-sequential way, which may involve creating another thread. For ...
0
votes
0answers
11 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 ...
-4
votes
0answers
26 views

In some circumstances, the choice of transactions to abort may be obvious [closed]

In some circumstances, the choice of transactions to abort may be obvious. However, in other situations, the choice may not be so clear. In such cases, we would want to abort the transactions that ...
0
votes
0answers
23 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 ...
1
vote
1answer
29 views

“Equality” problem in distributed computation

I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads). I have seen as a side note in a few lower bound proofs, a reference ...
0
votes
1answer
83 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
693 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?
2
votes
2answers
93 views

Ordering of operations in a DAG of git commits

Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug Summary of the current algorithm and shortcomings git-bug is a distributed bug-tracker that ...
4
votes
1answer
105 views

In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3?

The paper is available here: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf The 1st paragraph of lemma 3's proof says In other words,if event e is applicable to config C,and E is any ...
0
votes
0answers
38 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 ...
0
votes
0answers
12 views

Why does Chord maintain a finger table instead of entire membership list (using SWIM)?

Chord uses a finger table for querying, and it takes $O(\log n)$ to get the result. Why not maintain the entire membership list and get result in $O(1)$?
1
vote
1answer
110 views

Strong Uniform Total Order vs Weak Uniform Total Order

The definition for SUTO and WUTO is the following: Suto If some process TODelivers some message m before message mʹ, then a process TODelivers mʹonly after it has TODelivered m. And for WUTO ...
1
vote
0answers
13 views

Why is it considered hard to maintain strong consistency in a distributed system?

Why can't you just use strongly consistent reads for all your DB reads, with retries on 500 responses? According to CAP theorem increasing consistency should probably lower availability, but can't the ...
0
votes
1answer
29 views

How does Lamport imply anomalous behavior is impossible given these constraints?

Lamport's paper: Time, Clocks, and the ordering of Events in a Distributed System Anomalous behavior occurs because Lamport's logical clocks are not enough to guarantee that the total ordering of ...
0
votes
0answers
8 views

Ordering Multicasting in Distributed Systems

We know that Causal ordering in ordering multicasting implies FIFO ordering. But does FIFO ordering implies Casual Ordering?
0
votes
0answers
20 views

Correctness of Linearizability vs Sequential consistency in replication

I'm currently studying Sequential consistency vs linearizability: I know that SC has to be consistent with the order of how the individual client issued them, and for linearizability, it's with the ...
0
votes
0answers
11 views

Problem identifying concurrent Events

I have a number of vector timestamps and have to identify all concurrent events: I understand why (C, F) and (H,C) are concurrent events; They fulfill following condition: But shouldn't then also ...
1
vote
1answer
30 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 ...
0
votes
1answer
21 views

Why does the converse of the clock condition imply that any two concurrent events occur at the same time?

In Lamport's paper, Time, Clocks, and the ordering of Events in a Distributed System he says that the converse of the clock condition does not hold and if it did, we could expect concurrent events to ...
1
vote
1answer
89 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 ...
2
votes
1answer
35 views

Averaging a list of variances

In a setting where I have n clients each owns a subset of the dataset, each computes the mean and variance on his data and send them to the server. The server would average all means and variances. ...
0
votes
0answers
60 views

Two Generals' Problem Definition

I've read various descriptions of the TGP, most of which seem vague or conflicting on the precise constraints of the problem. Specifically: is it always or sometimes impossible to reach consensus ...
0
votes
0answers
10 views

Dynamic replica membership in a distributed causally-consistent database

Given a distributed causally-consistent database (a replicated key-value store where writes are propagated in causal order, in the style of this paper), what are common techniques for "scaling&...
2
votes
0answers
37 views

Using vector clocks vs. directed acyclic graph for causality detection in distributed systems

I'm trying to understand how vector clocks compare to DAGs for causality detection in a distributed system. When trying to detect causality relations in a distributed system, a very commonly proposed ...
0
votes
1answer
17 views

Method of communication in Distributed Systems

Why the method of communication used in DS is message passing and not shared memory ?
0
votes
0answers
14 views

Is there any guarantee in asynchronous systems?

We know that in an asynchronous system, no assumptions about process execution speeds or message delivery times are made. My question is: can we present any guarantee in asynchronous systems? Some ...
0
votes
1answer
21 views

How does random number probabilities work in distributed systems?

Let's say I have a code which does coin toss at 25% win probability. If I run this code n number of times in the same system it will yield ~25% win. If I run this code on n devices (once each) will ...
0
votes
1answer
14 views

What is the relation between a web server and a local file serve in distributed systems?

I am learning distributed systems ( although I am an Electrical engineer ) using the book distributed systems concepts and design. The author says that "A web server is often a client of a local ...
0
votes
0answers
15 views

MMOGs as an example of distributed systems

In the book "Operating System Concepts and Principles" , the authors mentions massively multiplayer online games as an example of Distributed Systems. They mention that as an example of ...
0
votes
0answers
10 views

Synchronization in Distributed Systems

If there is no global clock in Distributed systems , then what is the solution for synchronization in DS ? Also , no global clock in DS is a direct consequence of the fact that the only communication ...
3
votes
1answer
38 views

What is a distributed algorithm for generating random “private” pair-matchings?

Say you have 2N named peers (agents) able to address each other by their name and communicate freely among them. What distributed algorithm could they use in order to randomly pair up? The final ...
0
votes
0answers
18 views

Distributed Serializable Snapshot Isolation

I was wondering if there is any research on distributed transaction algorithms for Serializable Snapshot Isolation. I found Binnig, C. et al.: Distributed snapshot isolation: global transactions pay ...
0
votes
0answers
24 views

Why is shared register's consensus number 1?

I'm trying to understand the consensus number concept. It is trivially clear that a shared register doesn't create any problem when there is only one thread using it. By why does its consensus number ...
2
votes
1answer
29 views

Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric

I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The ...
2
votes
0answers
66 views

Why is the 'Integrity' property required in consensus protocols?

Formally a consensus protocol must satisfy the following three properties: Termination Eventually, every correct process decides some value. Integrity If all the correct processes proposed the same ...
3
votes
1answer
26 views

Randomly assign n elements to n agents such that each agent only knows its own element

Problem I'm working on an app that involves shuffling and distributing playing cards to players. As a challenge, I tried to solve this problem in a way that doesn't require a trusted intermediary. In ...
2
votes
1answer
63 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. ...
3
votes
1answer
326 views

determining timeouts / retry attempts in distributed systems

Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution ...
1
vote
1answer
81 views

Distributed predicate computation on event stream

My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work. I'm working on a program that computes a predicate value (true or false) for ...
10
votes
3answers
4k 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 ...
1
vote
0answers
19 views

Number of referee nodes required in distributed leader election algorithm

I know the reason as to why $O(\sqrt{n\log n})$ referee nodes are required. What I don't understand is how to arrive at that value, when I have $7\log n$ candidate nodes. Please forgive me if this is ...
1
vote
1answer
43 views

Confused between 2 phase locking and 2 phase commit

I understand that both algorithms are very different, but what I don't understand is whether they achieve the same thing in the end. 2PC is for atomic commits and 2PL is for serializable isolation. ...
4
votes
0answers
34 views

What are some advanced background topics I'll need for distributed systems and networks research?

I am a new graduate student in Computer Science who would like to be able to read and understand modern and new distributed systems research papers. My current background / courses and understanding ...
0
votes
0answers
5 views

What is the current definition for HPC systems - do they include both GPUs and MIMD Supercomputers?

I have seen several definitions across the internet and this question still bugs me.
2
votes
0answers
20 views

Finding the timestamps of processes implementing Lamport's clocks

I have been asked this question, but don't know how to go about answering it. Three process, which are implementing Lamport's clocks, are running and a lot of events are taking, place including some ...
63
votes
7answers
69k 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 ...
6
votes
2answers
2k views

Why is the commit phase in PBFT necessary?

I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that PREPARE phase ensures fault-...
0
votes
0answers
17 views

Count nodes with more than 3 neighbours in distributed computing, initiating by one site

I have an algorithm that visit all the nodes on a graph in distributed computing , the initiator is one site only , I want to change it so that the initiator can in the end of the execution know the ...
1
vote
1answer
76 views

Why is two-phase commit better than naive master-slave replication?

In the context of a distributed database, I'm trying to understand why 2PC (as described in e.g. https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/L6-2pc.pdf) is better than the ...
0
votes
0answers
14 views

What are the advantages of NHSX centralised protocol for Contact Tracing?

Apple and Google have published a protocol for privacy-presercing contact tracing - https://www.apple.com/covid19/contacttracing/ They use a decentralised approach where the 'matching' process take ...

1
2 3 4 5
7