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

Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
user avatar
0 votes
1 answer
23 views

Difficulty understanding how federation increases cache performance for databases?

I am studying system design for distributed systems and in this page (https://github.com/donnemartin/system-design-primer), one of the following advantages was mentioned for federation for databases ...
user avatar
  • 125
0 votes
1 answer
34 views

a question related to consensus number of a concurrent object

a) We know that solving consensus in asynchronous distributed systems is impossible. b) Let the consensus number of a concurrent object be cn = 2, which means that two processes can solve consensus ...
user avatar
1 vote
0 answers
45 views

Is there a distributed streaming algorithm to verify set cover?

I have $k$ sets of similar sizes, that cover a universe $U$. e.g. for $k=3$ and $U = \{1, 2, 3, 4, 5, 6\}$: $S_0 = \{1, 2, 4\}$ $S_1 = \{2, 3, 4\}$ $S_2 = \{4, 5, 6\}$ I have another larger set $C$ ...
user avatar
  • 123
2 votes
1 answer
27 views

How do distributed joins work in a distributed relational database system?

I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
user avatar
  • 1,853
0 votes
1 answer
23 views

Term for the total communicated data over a distributed system

I am looking for a publication-friendly term to describe the total quantity of data communicated between nodes of a distributed system, as invoked by some discrete operation. This term would describe ...
user avatar
0 votes
0 answers
13 views

How do relational algebra query analyzers generate query alternatives?

tl;dr: How does a query analyzer know how to modify a query to find a better one? I would like to implement a distributed database. I have figured out ways of storing data in a normalized form, and ...
user avatar
  • 1,853
0 votes
0 answers
34 views

Why can't we solve the consensus problem by just enforcing a new leader?

I am going through this lecture series by Martin Kleppman. In this video at around 1:25, he says you can manually configure the distributed nodes to chose a leader. If that's the case can't we just ...
user avatar
3 votes
1 answer
31 views

How does a single-node system get Availability in CAP theorem?

I have a question. I read many blogs, websites about CAP theorem. They say that single-node systems are CA, but how can it be "A" if that single node goes down ? Because if it does, the ...
user avatar
  • 31
1 vote
2 answers
39 views

What are good algorithms for distributed purchasing?

I'm looking for some algorithms/patterns to solve a distributed systems problem. Lets say I have created a trading platform buying stock (I haven't), and I have a distributed system of 50 nodes that ...
user avatar
  • 13
0 votes
1 answer
18 views

Does pattern matching require having the data on one machine?

Is it possible to use pattern matching algorithms such as FP-Trees and others on data that resides in multiple machines? Basically when doing pattern matching do you have to have all your data on the ...
user avatar
0 votes
0 answers
33 views

Does DHT (Distributed Hash Table) allow to list ALL (not only nearest) nodes?

As I know any local DHT keeps only some of nodes - if the network is small/very small then all nodes, otherwise only some of them (nearest?). So, when I checked different Golang implementations of DHT ...
user avatar
  • 101
0 votes
0 answers
18 views

Resources to self-study counting/sorting networks

I am reading The Art of Multiprocessor Programming. I was able to grasp almost everything up to Counting Networks in chapter 12 - Counting Sorting and Distributed Coordination. However I am having ...
user avatar
2 votes
0 answers
49 views

Is this simple Asynchronous Byzantine Consensus Protocol correct?

I'm trying to solve a problem that may arise in a system I am concerned with. It will be uncommon in practice, so I am more concerned about simplicity and correctness than performance. I have N ...
user avatar
1 vote
0 answers
31 views

Modern standard texts on distributed systems

I'm starting a job soon that involves a large number of disciplines interacting at once. I'm knowledgeable in most of these areas; at least enough that when I don't know something I know how to look ...
user avatar
  • 3,728
1 vote
0 answers
49 views

Can decentralised systems mitigate 51% attacks by design?

Can you make decentralised systems, e.g. cryptocurrencies or serverless games, that aren't susceptible to 51% attacks by design? (Rather than, as I've seen proposed, external solutions like fining ...
user avatar
1 vote
0 answers
25 views

Bully Algorithm Timeout After Receiving a Response from a Higher Process

Im specifically referring to the bully algorithm for synchronous systems, described in [Garcia-Molina 1982]. In it, the timeout for failure detection is concretely defined as the sum of the round trip ...
user avatar
2 votes
0 answers
19 views

Minimum number of registers for mutual exclusion

I was reading distributed algorithms (by Nancy lynch) and there is a part that I would kindly like to get a simpler explanation for. I know the book mentioned no algorithm can solve mutual exclusion ...
user avatar
0 votes
0 answers
24 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, ...
user avatar
  • 121
3 votes
1 answer
52 views

Proof in the "Reaching Agreement in the Presence of Faults"

I am reading the "Reaching Agreement in the Presence of Faults", M. Pease et al and trying to understand their proof for the $n \geq 3m+1$ case. In the induction step $m \gt 0$ it says the ...
user avatar
  • 31
0 votes
0 answers
25 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?
user avatar
0 votes
0 answers
64 views

What is the meaning of fault tolerant average?

I am studying about berkely algorithm in distributed system for clock synchronization and one thing that caught me was the term "fault tolerant average". Basically the average taken here is ...
user avatar
  • 9
0 votes
1 answer
101 views

What is the meaning of the pipe symbol here?

I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
28 views

How does clients observe different replicas and stale data even if the replicas include same set of updates?

I am studying about gossip architecture. This is gossip architecture-: Gossip architecture provides 2 guarentees-: 1)Each client gets consistent service over time(meaning even if clients use ...
user avatar
1 vote
1 answer
140 views

Invariant vs Assertion vs lemma

I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate ...
user avatar
1 vote
1 answer
379 views

How is this example sequentially consistent but not linearizable?

Background information that I know(But not understand with examples, I will be glad if you could explain it to me with examples) A replicated service is said to be linearizable if for any executin ...
user avatar
0 votes
0 answers
43 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 ...
user avatar
  • 73
0 votes
0 answers
27 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 ...
user avatar
  • 73
1 vote
0 answers
13 views

Distributed Graph Consensus to fit a distribution?

$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance. The objective is for ...
user avatar
  • 389
1 vote
0 answers
83 views

How is this example related to Lamport clock theory? I can't relate algorithm example with the algorithm theory. Share some insights please [closed]

I have asked 1 type of question but I have asked that in many questions. So bear with me. My question is about 1 topic, I just didn't find it right to create separate questions for each of these ...
user avatar
-1 votes
1 answer
56 views

If primary server's UTC source fails, how will synchronization be possible in NTP(network time protocol)?

If a primary server's UTC source fails, then it can become a stratum 2 secondary server. If a secondary server's normal source of synchronization fails or becomes unreachable, then it may synchronize ...
user avatar
1 vote
2 answers
43 views

What is an example of an algorithm that requires synchronised clocks?

What is an example of an algorithm that requires synchronised clocks? Synchronised in an absolute sense, not just synchronised clock rates. For more background, I've read Barbra Lisksov's 1993 paper '...
user avatar
1 vote
2 answers
505 views

Algorithm notation

I am reading Nancy Lynch's Distributed Algorithms. In page 103, there is the FloodSet algorithm. Can anyone please explain what Uj mean in W := W U Uj xj (line 3 of transition function)?
user avatar
0 votes
0 answers
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 ...
user avatar
  • 11
2 votes
2 answers
44 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 ...
user avatar
  • 389
0 votes
0 answers
51 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 ...
user avatar
  • 101
1 vote
1 answer
176 views

What's the difference between a protocol and a distributed algorithm?

What's the difference between a protocol and a distributed algorithm? My internship supervisor told me they are not exactly alike. A protocol is more communication-oriented (e.g. TCP), whereas a ...
user avatar
0 votes
0 answers
21 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 ...
user avatar
  • 33
0 votes
0 answers
18 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 ...
user avatar
  • 33
1 vote
0 answers
38 views

What is the difference between Swarm intelligence and Multiagentsystems?

Swarm intelligence and Multiagent systems are both a part of Distributed AI. Multiagent systems describe a system with agents, which communicate with each other. Swarm intelligence describes systems, ...
user avatar
  • 111
0 votes
0 answers
32 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, ...
user avatar
1 vote
2 answers
77 views

What is the difference between broadcast and gossip/epidemics?

Everything is in the title. What is the difference between broadcast and gossip in the context of message-passing distributed systems? According to Wikipedia, gossip and epidemic protocols/epidemics ...
user avatar
0 votes
1 answer
73 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 ...
user avatar
  • 31
1 vote
0 answers
24 views

Really confused about the chord algorithm

I'm looking at the pseudocode for chord algorithm here: ...
user avatar
  • 123
1 vote
0 answers
49 views

Can old hardware be practically useful for CS problems of modern day?

Thinking about specific settings on WorldBuilding.SE, it turns out I need help from people who are more in touch with CS and Clusters. For those who curious about how it started, backstory here, ...
user avatar
  • 111
2 votes
1 answer
43 views

Distributed transaction problem

Let's suppose there are two banks, Bank A and Bank B. A transaction needs to happen that transfers money from an account in Bank A to an account in Bank B. Bank A and Bank B have separate banking ...
user avatar
0 votes
1 answer
28 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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
43 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 ...
user avatar
  • 10.7k

1
2 3 4 5
8