We changed our privacy policy. Read more.

Questions tagged [distributed-systems]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
25 views

Can smoothed analysis be studied on the batch dynamic model?

I was reading about the batch dynamic CONGEST model for distributed computing. This model assumes a fixed communication network, but where local inputs to nodes may change over time. It aims to study ...
0
votes
0answers
21 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
18 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 ...
0
votes
1answer
90 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 ...
0
votes
0answers
12 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
1answer
24 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 ...
1
vote
1answer
102 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 ...
1
vote
0answers
265 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 ...
0
votes
0answers
160 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
14 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 ...
1
vote
0answers
11 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 ...
1
vote
0answers
69 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 ...
-1
votes
1answer
36 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 ...
0
votes
0answers
24 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 ...
1
vote
2answers
39 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 '...
1
vote
2answers
492 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)?
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
37 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
108 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
31 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
26 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
34 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
52 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
48 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
21 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
26 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
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 ...
1
vote
1answer
35 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
37 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
131 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
73 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
53 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
27 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
38 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
27 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
17 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
40 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 ...

1
2 3 4 5
8