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
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
20 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 ...
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 '...
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
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 ...
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 ...
1
vote
1answer
406 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
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 ...
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 ...
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-...
1
vote
1answer
95 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 ...
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
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
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
1answer
28 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
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 ...
2
votes
3answers
387 views

What is so special about a majority and why is it the key for Paxos to work? (Paxos made simple)

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values. I was studying Paxos from: http://...
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 ...
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 ...
13
votes
4answers
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
1answer
107 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
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
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 ...
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
1answer
93 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 ...
1
vote
1answer
880 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?
4
votes
1answer
119 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
25 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
33 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 ...
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
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 ...
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
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, ...
13
votes
3answers
4k views

What is the origin of the client server model?

I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?
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
2 3 4 5
8