Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
352
questions
-2
votes
0answers
22 views
CORBA,MACH,JINI,TIB Rendezvous-: From where do I learn about these things? [closed]
I searched a lot but could not find much information related to these topics. Can someone guide me.
https://slideplayer.com/slide/4998505/
https://surajawal.pythonanywhere.com/note/distributed-system/...
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
21 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
36 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 ...
1
vote
1answer
88 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 ...
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 ...
1
vote
0answers
29 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, ...
0
votes
0answers
24 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, ...
1
vote
1answer
31 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 ...
0
votes
0answers
42 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
44 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 ...
1
vote
0answers
19 views
Really confused about the chord algorithm
I'm looking at the pseudocode for chord algorithm here:
...
1
vote
0answers
43 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, ...
2
votes
0answers
19 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 ...
0
votes
1answer
25 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
13 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
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
34 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
0answers
39 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 ...
1
vote
0answers
14 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
0answers
9 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
1answer
34 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
12 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 ...
2
votes
2answers
126 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 ...
0
votes
0answers
70 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
11 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
49 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
26 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 ...
2
votes
1answer
37 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
1answer
25 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
15 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
1answer
34 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
1answer
46 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 ...
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 ...
1
vote
1answer
23 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 ...
0
votes
1answer
21 views
Method of communication in Distributed Systems
Why the method of communication used in DS is message passing and not shared memory ?
3
votes
1answer
39 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
26 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
29 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
30 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
78 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
27 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 ...
1
vote
1answer
83 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 ...
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
180 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
35 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 ...
2
votes
0answers
23 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 ...
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 ...
