Questions tagged [distributed-systems]

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

133 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
82 views

Distributed Storage for Access and Preservation

My organization wants to maintain multiple copies of data in order to preserve access in the case of localized disasters as well as for the purpose of long term preservation. Are there accepted formal ...
6
votes
0answers
92 views

What is 2g-precedence?

I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much ...
5
votes
0answers
42 views

Uni-directional synchronization and locking issues

Suppose there are two databases, $D_1$ and $D_2$. Let's further assume $D_1$ is always up and $D_2$ can be down sometimes. When it goes up again, it has to restart. $D_1$ is filled by say a dozen ...
4
votes
0answers
43 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 ...
4
votes
0answers
74 views

What distributed consensus algorithms don't rely on a time source?

I'm looking for information about distributed consensus algorithms that: maintain a consistent transaction log across all healthy nodes have similar high-availability properties to Paxos (i.e. not ...
4
votes
0answers
730 views

Even distribution algorithm

Right now I am working on a distributed system that sends messages from single source to many nodes. It is necessary that certain messages are sent to the same node to ensure order of processing. ...
4
votes
0answers
530 views

Is there any theory behind GraphQL?

GraphQL is a query language for your API, and a server-side runtime for executing queries by using a type system you define for your data. Source: http://graphql.org/learn/ So GraphQL allows a ...
4
votes
0answers
58 views

How to realize a distributed queue with unreliable participants?

I want to build an application that relies on a distributed queue with participants in a decentralized (peer-to-peer) network. The participants cannot be relied on to correctly follow a protocol. I ...
4
votes
0answers
107 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
4
votes
0answers
63 views

Extending the causal memory model to wide-area distributed storage systems

In the seminal paper "Causal memory: definitions, implementations, and programming", distributed causal memory is defined to ensures that all the processes in a system agree on the relative ordering ...
3
votes
0answers
19 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 ...
3
votes
0answers
47 views

Why does the proposer sends an accept request with the same value it got from the acceptor?

In the second phase of the paxos algorithm, the proposer issues an accept request with the number n and the value v it got from ...
3
votes
0answers
126 views

What are the theoretical and practical contributions of Multiagent Systems to science?

Speaking about multiagent systems (MAS) is about as fuzzy as talking about artificial intelligence systems (AI). They are in essence the distributed counterpart of AI. While there are no so-called "...
3
votes
0answers
640 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following,...
3
votes
0answers
5k views

totally ordered multicast with Lamport timestamp

I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the ...
3
votes
0answers
128 views

Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)

I was studying Paxos from: http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf Recall that Paxos is a distributed system algorithm with the goal that the processes ...
3
votes
0answers
164 views

Proof of message complexity on the network

I try to provide a strict and mathematical rigorous proof to the following problem in Distributed Algorithms. Prove or make a contradiction: if to vertices $a$ and $b$ on the network $G$ are located ...
3
votes
0answers
71 views

How is amorphous computing different from spatial computing?

Surely spatial computing and amorphous computing share similarities and overlap. Is spatial computing a subset of amorphous computing? How are the two different?
2
votes
0answers
42 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
476 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
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
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
0answers
6 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 ...
1
vote
0answers
47 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 ...
1
vote
0answers
26 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 ...
1
vote
0answers
22 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 ...
1
vote
0answers
306 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
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 ...