Questions tagged [distributed-systems]
Questions about the challenges of solving problems with multiple cooperating but separate agents.
111
questions with no upvoted or accepted answers
8
votes
0answers
77 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
86 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
37 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
67 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
88 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 ...
4
votes
0answers
400 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
486 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
104 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
62 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
46 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
52 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 ...
3
votes
0answers
108 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
485 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
4k 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
115 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
163 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
70 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
40 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
29 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
0answers
29 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
38 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
71 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
145 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
1answer
297 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
110 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
51 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
61 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
64 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
53 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
44 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
43 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
282 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
71 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
11 views
Arbitrary fault abstraction in 'Reliable and Secure Distributed Programming'
In the book by Cachin, Guerraoui, Rodrigues they discuss an arbitrary fault abstraction. It seems to me that this abstraction does not include crashes in its behavior. I think this because they ...
1
vote
0answers
23 views
What are the correlation between Actor model and Reactive Programming
Could anyone explain the difference/relation between the Actor model and Reactive programming?
It seems that they are located at different levels of abstraction - one can design the interaction ...
1
vote
1answer
19 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 ...
1
vote
0answers
20 views
Byzantine Generals Problem - Regular Set of Neighbors
Going through Lamport's paper, I'm a little confused by the second part of the regular set of neighbors definition.
A set of nodes $\{i_1, \ldots, i_p\}$ is said to be a regular set of neighbors ...
1
vote
0answers
36 views
Byzantine Generals Problem - Oral and Signed Messages
Having just read through Lamport's paper, I was hoping someone could clarify a few things on the Oral and Signed message algorithms.
Why do we have to run $OM()$, recursively by $m$? If a majority of ...
1
vote
0answers
64 views
Paxos algorithm, accept phase
From the wiki https://en.wikipedia.org/wiki/Paxos_(computer_science)
If a Proposer receives enough Promises from a Quorum of Acceptors, it needs to set a value v to its proposal. If any Acceptors ...
1
vote
0answers
26 views
Resetting Vector clocks in distributed systems
I understand that vector clocks are preferred over lamport clocks because sometimes lamport clocks cannot account for the casuality and we use extra space to store the timestamps in the vector clocks.
...
1
vote
1answer
77 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 ...
1
vote
0answers
19 views
Problem of making entities agree on some wavelength
I remember seeing this problem somewhere before, but don't remember what it's called and can't find it again.
It was presented as two guys having $n$ phones each that don't ring when called. Each ...
1
vote
0answers
67 views
A tree-like data structure with rights delegation for distributed computing
Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...
1
vote
0answers
31 views
Why in the Map Reduce Implementation, why not stream the records to the reducer (via TCP) as they are being produced by the mappers?
In the Map-Reduce implementation, the reducers start when all mappers finish their jobs. Why don't we stream the records from mappers to reducers while they are being processed instead? I think there ...
1
vote
0answers
58 views
How do distributed algorithms for shortest path finding handle negative cycles?
I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
1
vote
0answers
27 views
Why don't RDBMS use a quorum based solution to do failover
For RDBMS viz. MySql, PostgreSql a common solution for scalability and high availability is to run a primary instance as master that is a read-write instance and one or more read replicas. If the ...
1
vote
0answers
67 views
Strong Uniform Total Order vs Weak Uniform Total Order
The definition for SUTO and WUTO is the following:
Suto
If some process TODelivers some message m before message mʹ, then a process TODelivers mʹonly after it has TODelivered m.
And for WUTO
...
1
vote
0answers
32 views
Tendermint Consensus - Resilient up to 1/3 of Byzantine participants
Tendermint Consensus is resilient for up to 1/3 of Byzantine participants.
Question: What actually happens after when the network hits the threshold of byzantine actors? Forking happens? Does ...
