Questions tagged [distributed-systems]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
47 views

Term for shifting work to idle machines

I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks ...
2
votes
1answer
56 views

How to make a "Secure by Design" client-server communication?

Is there a way to have a secure by design client-server communication in a sense that the server can check if the client is not a modified version? What I'd like to do is give the user access to both ...
2
votes
1answer
112 views

In Paxos, what prevents multiple values from being chosen?

Say we have two proposers (P1, P2), one acceptor (A), and two learners (L1, L2). What would prevent this sequence of events from occurring? P1 initiates a round numbered 1. A agrees to participate, ...
2
votes
2answers
309 views

Why does an acceptor send the highest numbered proposal with number less than n as a response to prepare(n) in paxos?

I was reading the Paxos notes from yale from the following link: http://pine.cs.yale.edu/pinewiki/Paxos Recall that Paxos is a distributed system algorithm with the goal that the processes ...
2
votes
1answer
226 views

How do we make sure in Paxos that we don't propose a different value if a majority has formed?

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://...
2
votes
1answer
54 views

What is the difference between E-Science Infrastructures and Distributed Computing Infrastructures?

What is the difference between eScience infrastructures and grid computing or distributed computing infrastructures? And what are some of their examples. I can not distinguish them clearly. Is it how ...
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. ...
2
votes
1answer
75 views

Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
2
votes
1answer
269 views

Async Distributed Algorithm Time Complexity

In theory of distributed systems, I understand message complexity and time complexity are common performance measures, with the first being the number of messages sent in the overall execution of the ...
2
votes
1answer
45 views

Soft question: program result verification

Let's say there's a cloud computing service that allows people to run arbitrary programs and get the results. The idea being that your machine is too slow, and you don't want to overwhelm it. If your ...
2
votes
1answer
163 views

Classification of technologies used for communication in distributed systems

I am currently writing a State of Art about technologies used for distributed communication (like CORBA for example). I want to structure the document in way that I don't leave any subset of this ...
2
votes
1answer
571 views

Working of the GHS algorithm

Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found ...
2
votes
1answer
223 views

Difference between BSP model and synchronous round model in distributed computing

I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens: every node can send a message to ...
2
votes
1answer
5k views

Clock skew vs clock offset in the context of clock synchronization network protocols

In the context of clock synchronization among nodes of a network, what is clock offset and what is clock skew? Are these terms synonymous or is there a difference between them?
2
votes
1answer
60 views

How P2P search engines prevent corruption of distributed index by malicious peers?

As a hobby, I am writing a simple and primitive distributed web search engine. It occurred to me that it currently has no protection against malicious peers trying to skew the search results. The ...
2
votes
1answer
450 views

Maximimal Independent Set on Ring and Path

Let's consider distributed version of algorithm for finding MIS of any graph $A$. For details, MIS - Maximimal Independent Set. Slow version of distributed algorithm for MIS, page 2 - Distributed ...
2
votes
1answer
926 views

Impossibility condition in the Byzantine Generals problem

I am unable to understand why there is a requirement of 3m+1 generals overall given m traitors. As per my understanding, the steps are as follows: Each general decides a strategy and forwards their ...
2
votes
0answers
43 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 ...
2
votes
0answers
15 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 ...
2
votes
0answers
25 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 ...
2
votes
2answers
148 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 ...
2
votes
0answers
63 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 ...
2
votes
0answers
99 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 ...
2
votes
0answers
27 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 ...
2
votes
0answers
67 views

Leader election in synchronous ring with unreliable communication channels

As a part of my Distributed Systems course I am required to provide an algorithm that is able to elect a leader in a synchronous bidirectional ring, where every message that is sent may be lost (lets ...
2
votes
0answers
36 views

Distributed algorithms for finding n largest elements

It's easy to come up with a simple distributed algorithms for finding the maximum element in a set (totally ordered): Divide and conquer. There are a few publications that present algorithms for ...
2
votes
1answer
480 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 ...
2
votes
0answers
58 views

Distributed Computing: Persistent Data Structures in Functional Programming versus Wait-Free Data Structures

Persistent (aka immutable) data structures in functional programming sidestep issues of shared memory mutual exclusion, and thus also issues such as data races that arise and which may be difficult to ...
2
votes
0answers
41 views

Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= nodes). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
2
votes
0answers
77 views

Why is a primary node needed in pBFT algorithm for consensus?

Why is primary needed in pBFT algo? Since many issues of viewchange etc. come up because primary may be faulty - is it possible to have a version of pBFT which doesn't have nodes assigned as primary? ...
2
votes
0answers
181 views

Byzantine generals (n=3, m=1)

Leslie Lamport describes a algorithm to come to consensus for the case for n>3*m, there m is the number of traitors in ...
2
votes
0answers
632 views

How to compare distributed systems and big data

Are there scientific papers that compare distributed systems and big data processing systems? Big data processing systems can be batch processing systems or streaming big data processing systems. A ...
2
votes
0answers
117 views

Are Synchronous Message Order and Total Message Order separate concepts?

I am currently studying this book on distributed systems. In the chapter on message ordering the authors appear to use the term total message ordering and synchronous message ordering interchangeably. ...
2
votes
0answers
57 views

Auction website with Paxos consensus algorithm

As a project, I'm trying to construct a P2P auction web application with paxos in a high latency environment. The idea is that each user visiting the website will keep a small log file with the ...
2
votes
0answers
62 views

Distributed consensus feasibility from graph structure

Consider a consensus process in which participants Initially take a position Receive positions only from their neighbors Accept a new position that is a super-majority of neighbors positions. Under ...
2
votes
0answers
72 views

What is the largest number of Byzantine failures that can be tolerated in an $m$-dimensional hypercube for the consensus problem?

We are given a system with $n$ nodes which have been arranged into the topology of a hypercube of $m$ dimensions. I would like to derive a tight bound on the maximum number of Byzantine failures that ...
2
votes
0answers
61 views

Floating output/making a non-self stabilizing algorithm self stabilizing

So we're using this book by Shlomi Dolev on self-stabilization in class. Not being from a theretical CS background, I think the book is rather terse. Most of it is fine but there's this section on "...
2
votes
0answers
99 views

What are the prerequisites for working on multi agent systems? [closed]

I am starting to study about Multi Agent Systems and I wanted to know which sciences are most used in these systems, I am aware of game theory and Markov statistical relations (Markov Decision Process ...
2
votes
0answers
79 views

Client-Server Architecture /State Model and Process Mode [closed]

how i can define what are Client-Server Architecture for a website that suggestion courses for students after students insert the history of courses. The language will be PHP,mysql and HTML. In this ...
2
votes
0answers
56 views

Find the size of the maximum cycle in a MPS

Consider the following problem to be solved in a distributed context: Find for each processor the size of the biggest cycle of which it is member. My algorithm is the following (for synchronous ...
2
votes
0answers
50 views

Distributed push relabel with changing graph topology

There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. ...
2
votes
0answers
1k views

How are Distributed Snapshot algorithms (likes of Chandy Lamport) implemented in real world distributed systems? [closed]

Can anyone explain, how Distributed Snapshot algorithms ( Example: Chandy-Lamport are implemented in the context of modern distributed systems? Can you name an open source System implementation ...
2
votes
0answers
46 views

Polylogarithmic value-bounded concurrent data structures such as max register, counter, and monotone circuit

While reading the research paper Polylogarithmic Concurrent Data Structures from Monotone Circuits [@JACM'2012] by James Aspnes, Hagit Attiya, and Keren Censor-Hillel, I am not sure about some points ...
2
votes
0answers
287 views

Efficiently estimating latency quantiles of a distributed system

I'm building a load test harness for a distributed system. Currently I'm using the "Cormode, Korn, Muthukrishnan, and Srivastava" method to estimate latency quantiles of system responses. I'm now ...
2
votes
0answers
72 views

Throughput measure

I have to implement a limitation algorithm in order to avoid to reach a throughput limit imposed by the service I'm interacting with. The limit is specified as «N request over 1 day» where N is of ...
2
votes
0answers
1k views

k-Trees Graph Coloring

There is an exercise in Distributed Algorithm I have some difficulties to solve. There are few ideas, however nothing useful at the time. I will appreciate any help with it. Graph $G$ is a $k$-tree ...
1
vote
2answers
500 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)?
1
vote
1answer
248 views

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used ...
1
vote
1answer
121 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
1answer
42 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 ...

1 2 3
4
5
8