Questions tagged [distributed-systems]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
87 views

FLP Impossiblity Result assumption of $C_1 = e'(C_0)$

FLP86's famous proof regarding impossibility of async distributed processes with a single fault assumes in the proof of the third lemma the existence of an event $e'$ such that the neighbor ...
3
votes
1answer
75 views

affinity based static load balancing

I am trying to find a good model the following problem: Given a collection of work packets x, y, z, ..., and a collection of worker nodes ...
3
votes
2answers
236 views

Paxos made simple -- two details

I'm missing two details from Paxos made easy P1. An acceptor must accept the first proposal that it receives. What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon ...
3
votes
1answer
101 views

Contamination in Atomic Broadcast in crash stop failure model

I'm reading several papers about different broadcast algorithms. Most of them are designed for crash stop model but they also consider contamination scenarios. For example for a Causal Atomic ...
3
votes
1answer
241 views

Is per-record timeline consistency is somehow equivalent to causal consistency?

What I understand about per-record timeline consistency is: For a specific primary key all the insert/update/delete operations should be read in the same order by all replicas. Since all ...
3
votes
1answer
691 views

Best data structure for storing an ordered list, where each item is located on a separate server?

I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible. ...
3
votes
1answer
460 views

Paxos: Instances, Rounds, Phases

In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a $prepare$ phase, and an $accept$ phase. An instance of Paxos can have multiple rounds. Can a round have multiple ...
3
votes
1answer
94 views

What is the size of a queue associated with a resource when the resource becomes a bottleneck?

In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the ...
3
votes
1answer
1k views

What is the standard way to choose a new leader in Multi-Paxos?

If you are unfamiliar with multi-Paxos or paxos, the following link might be a good refresher on it: http://amberonrails.com/paxosmulti-paxos-algorithm/ or the paper by Leslie Lamport: http://...
3
votes
1answer
101 views

What is a "wasteful" execution? And a "schedule"?

I'm trying to understand what this text means in my textbook about distributed leader election algorithms, but I can't make any sense of it. Either they didn't explain what was meant, or I missed it ...
3
votes
1answer
357 views

Slow MIS Distributed Algorithm

I am interested in precise time complexity of distributed algorithm for finding MIS (Maximum Independent Set) of a given graph $G$. I investigate the Slow MIS distributed algorithm (from these ...
3
votes
1answer
38 views

Proof in the "Reaching Agreement in the Presence of Faults"

I am reading the "Reaching Agreement in the Presence of Faults", M. Pease et al and trying to understand their proof for the $n \geq 3m+1$ case. In the induction step $m \gt 0$ it says the ...
3
votes
1answer
600 views

What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?

After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages ...
3
votes
1answer
219 views

Impossibility of Distributed Consensus with One Faulty Process

I'm reading Fischer et al.'s Impossibility of Distributed Consensus with One Faulty Process, and I don't quite follow 2 points: The first is in the proof of Lemma 3, pg. 378: Otherwise, $e$ was ...
3
votes
1answer
259 views

Is it possible to write a wait free leader election algorithm?

I want to understand if there exists an algorithm which is wait free and operates on non-shared memory, asynchronously. Finally I want to know how to derive the consensus number of this algorithm. ...
3
votes
1answer
141 views

Understanding the fundamentals of building an in-Memory Distributed Graph

I am working on a project where I have to build an in-memory distributed graph capturing the relation between similar files(based on some similarity metric) stored in shared file system over multiple ...
3
votes
1answer
165 views

Residence time in multi server system

I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is: ...
3
votes
1answer
347 views

determining timeouts / retry attempts in distributed systems

Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution ...
3
votes
1answer
274 views

Consensus and Perfect Failure Detector

I try to get a better understanding about Failure Detectors in the field of Distributed Computing. Let consider the algorithm for reaching consensus with Perfect Failure Detector, it's named as ...
3
votes
1answer
653 views

Coordinated Attack Problem On The Arbitrary Graph

Let consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack. ...
3
votes
1answer
9k views

Destination-based vs source-based routing

I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-...
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
639 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
260 views

Widely-used and fundamental distributed algorithms [closed]

I've been reading text books about distributed algorithms. They usually present a large collection of algorithms under various hypothesis and guarantees, with their proof of correctness. But they ...
3
votes
1answer
101 views

Distributed problems in Financial Services?

When we talk about distributed computing - it often refers to problems in biology or web search where there is a large quantity of data to process, or email where there is a large number of concurrent ...
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
1answer
372 views

Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

In distributed systems we use the Chord algorithm to create a p2p distributed hash table. While this algorithm is very useful and efficient wouldn't it be better if we used an AVL tree? Chord ...
2
votes
2answers
2k views

What is the difference between consensus and mutual exclusion in Distributed Systems?

If we can achieve consensus, does it imply we can achieve mutual exclusion? Is there a difference? Example : Paxos solves the consensus problem, can it also be used to solve mutual exclusion?
2
votes
1answer
255 views

What can distributed computing do besides parallel computing?

I have some experiences of working on clusters and grids for parallel computing. But I wonder what distributed computing can do besides parallel computing? If I understand correctly, parallel ...
2
votes
1answer
62 views

Input distribution in FLP Impossibility

Lemma 2 in "Impossibility of Distributed Consensus with One Faulty Process" is as follows: LEMMA 2. P has a bivalent initial configuration. They prove this by showing that the opposite assumption ...
2
votes
1answer
110 views

Are there any types of distributed databases which allows untrusted peers, like Blockchain?

Are there any types of distributed databases which allows untrusted peers, like Blockchain? If it exist, can I look its whitepapers and/or implementations?
2
votes
2answers
3k views

What does atomicity mean in distributed systems?

In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem? Does atomicity have a different meaning in this context?
2
votes
1answer
173 views

How to interpret the execution of distributed computation from time-space diagram?

I'm following a course on Distributed Systems http://www.ict.kth.se/courses/ID2203/index.html and currently learning about asynchronous models. I can't seem to reconcile a given time-space diagram ...
2
votes
1answer
134 views

What's an "applicable event" in the context of the FLP paper?

I am reading Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382, available ...
2
votes
3answers
400 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://...
2
votes
1answer
57 views

Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric

I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The ...
2
votes
2answers
135 views

Why is there no extensive Standards Body overseeing ISAs, Bitcodes, Code Representation, etc... as there is in the case of Unicode

There exist a vast array of prominent bitcode formats, each suited for their specific task: LLVM IR: This format is build around a XML like binary streams model, designed to be used as a common ...
2
votes
1answer
134 views

What are the recents topics of research that combine both systems research and theoretical computer science?

I am an undergraduate majoring in Computer Science and Mathematics. For my undergraduate research, I would like to work on something that lies in the overlap between systems research and theoretical ...
2
votes
2answers
113 views

Sequential History in Herlihy and Wing's Linearizability paper

I've been reading Herlihy and Wing's paper Linearizability: A Correctness Condition for Concurrent Objects (ACM Transactions on Programming Languages and Systems, 12(3):463–492, 1990; PDF) and ...
2
votes
1answer
264 views

Theory of message complexity analysis of distributed systems

Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems - While most of us are familiar with the notion of Time Complexity as a ...
2
votes
1answer
197 views

Consensus anomaly about read-write registers and test&set

I read this answer below and got into another question. Why is the consensus number for test-and-set, 2? I also read that read/write registers have consensus number 1. But I see that in test&...
2
votes
2answers
169 views

outside of bitcoin, how does a network negotiate what the next blockchain should be?

There are two problems I see with negotiating the next block chain: which transactions to include in the chain (because consider transaction T which has propagated through exactly 49% of the network ...
2
votes
1answer
60 views

Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?

During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these ...
2
votes
1answer
38 views

How can a distributed system cooperate to determine rules of its environment?

I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm ...
2
votes
1answer
526 views

Call-by-reference semantics for RPC

Does call-by-reference semantics for remote procedure call (RPC) have a real use case? Why does call-by-reference RPC exist? Is it useful for anything? Is there a scenario where call-by-value can't ...

1 2
3
4 5
8