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
192 views

What does it mean that numbers are “totally ordered”, in the Paxos Made Simple paper?

I was studying Paxos from the paper by Lamport called "Paxos Made Simple". Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will ...
2
votes
2answers
262 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
2answers
540 views

How does FDS (flat datacenter storage) make optimizations around locality unnecessary?

I was reading the following computer systems paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf And I was trying to understand why it claims that it does not need data ...
3
votes
1answer
143 views

Why does appending permutations of servers at the end of hash table avoid bottlenecks?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf The paper has a TLT (tract locator table) for identifying where to write in each ...
3
votes
1answer
67 views

Why does the following function distribute things in a binomial distribution?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf and it says that the the following hash function does not distribute things uniformly ...
1
vote
0answers
70 views

simulation of Randomized distributed algorithms [closed]

I want to implement various Randomized Distributed algorithms for MIS, Broadcast, Coloring in Radio Networks. I want use very high level language or any simulator for this. Please suggest on this.
4
votes
1answer
1k views

Lamport's Byzantine Generals Algorithm

I've stumbled at the first OralMessage algorithm in Lamport, et al's paper. I've searched the web and there are dozens of sites, restating in exactly the same terms and examples, which isn't helping ...
3
votes
0answers
249 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 ...
2
votes
0answers
42 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 ...
1
vote
1answer
36 views

In a BOINC project, how are responses checked for accuracy? [closed]

More specifically, how can project administrators be sure that the answers they receive from nodes are correct and not just simple calculations performed quickly and submitted as complete work units? ...
2
votes
1answer
243 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 ...
1
vote
0answers
119 views

Differences in services provided by grid computing and cloud computing [closed]

What are differences in services provided by grid computing and cloud computing? From http://ccskguide.org/cloud-computing-vs-grid-computing/ and http://www.ibm.com/developerworks/web/library/wa-...
2
votes
0answers
280 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 ...
3
votes
3answers
2k views

Maximum degree of concurrency in task dependency graphs

I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find ...
0
votes
1answer
360 views

Distribution algorithm according to weighted parameters (with a min-max constraint)

I'm trying to solve the following problem related to distribution- I have a list L of items (I1, I2,....In) sorted in order of importance, I1 being the most important. Each item has multiple tags ...
1
vote
0answers
269 views

Peer discovery: What class of network algorithm prioritises low latency above all else?

I'm trying to flesh out a proposed application model where all peers in a distributed network discover each other in the least possible propagation time. But I'm reached the limit of my knowledge of ...
6
votes
2answers
2k views

Why do you have to worry about cache coherence if you are using shared memory?

Wikipedia says that shared memory comes with lots of costs associated with cache coherence costs. But I thought the whole idea of shared memory is that all the CPUs access the same memory? So if one ...
3
votes
1answer
98 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 ...
7
votes
2answers
150 views

Theoretical foundations of robust and distributed services

I have the notion of a social network which is robust against malicious attacks from the outside. My vision is a system that is structurally built up as a distributed network of equal servers that ...
0
votes
1answer
470 views

Coordinated Attack Problem Different Requirements

There is a famous Coordinated Attack Problem. Let define a simple message-passing system $S$ with requirements Uniform Agreement: No two processes decide dierently. Validity: (a) If all processes ...
3
votes
1answer
255 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 ...
1
vote
2answers
43 views

Broadcast with Limited Spreading

Let consider well-known problem in distributed computing Broadcast Problem in network with stopping crashes. The most appropriate solution to the broadcast problem is flooding algorithm, when the ...
3
votes
1answer
573 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
78 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 ...
15
votes
1answer
523 views

Who are the legislators of Paxos?

In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol. According to this ...
3
votes
1answer
126 views

Principles of Distributed Computing - “processors” and “states”

So I'm learning about distributed computing, and I do understand a lot of the prerequisite material on algorithms and automata and whatnot... but I'm curious about the definitions I'm seeing as I read ...
3
votes
1answer
157 views

Is this simplified consensus problem easier than the original?

There is a famous Consensus Problem in Distributed Computing. Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem. Assumptions: a process ...
10
votes
1answer
201 views

Formalisms in concurrent and/or distributed programming?

My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional ...
7
votes
2answers
99 views

Algorithm of Communication with Failures

I am interested in Distributed Algorithms especially in communication in network with failures. I look for the proof of the following randomized algorithm of communication in network with failures. ...
1
vote
0answers
44 views

Is this protocol suitable for transaction services?

The paper Eventually-Serializable Data Services (PODC'96) presented an eventually-serializable data service. In the abstract, it says: … and generalizes their algorithm (in the related work Lazy ...
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 ...
3
votes
1answer
7k 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-...
8
votes
2answers
949 views

6-coloring of a tree in a distributed manner

I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time. The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse ...
3
votes
1answer
325 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 ...
30
votes
2answers
8k views

How do Functional Reactive Programming and the Actor model relate to each other?

FRP is about streaming events and behaviours through pure functions. The Actor model - at least, as implemented in Akka - is about streaming immutable messages (which can be considered to be discrete ...
2
votes
1answer
416 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
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
1answer
234 views

Label Assignment Problem

I try to solve an exercise in Distributed Algorithm described as follow. Let's define a label assignment problem as follow. There is a anonymous network (vertices don't have unique ID's , nodes don't ...
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 ...
4
votes
1answer
1k views

Distributed 6-color Vertex Coloring

I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10). Here is a short description Idea of the algorithm: We start with color labels that have $\log n$ bits. ...
4
votes
1answer
1k views

How partitioning in map-reduce work?

Assume a map-reduce program has $m$ mappers and $n$ reducers ($m > n$). The output of each mapper is partitioned according to the key value and all records having the same key value go into the ...
0
votes
1answer
358 views

Static access pattern in Distributed Databases

The access patterns of user requests may be static, so that they do not change over time, or dynamic. It is obviously considerably easier to plan for and manage the static environments than would ...
13
votes
3answers
3k 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)?
4
votes
1answer
636 views

Distributed algorithms - $\alpha, \beta$ synchronizers

I experience a difficulty in solving exercises in distributed algorithm. Below is the the exercise I try to solve, it looks like I miss basic idea. Exercise. Consider a 15-processor asynchronous ...
2
votes
1answer
48 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 ...
24
votes
7answers
13k views

Start learning about Theory of Distributed Systems?

What's the best way that anyone can do to have a good introduction to the theory of distributed system, any books or references, and topics should be covered first and requirements to start learning ...
2
votes
1answer
842 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 ...
3
votes
0answers
69 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?
68
votes
4answers
16k views

What is the novelty in MapReduce?

A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1] The name is ...
7
votes
1answer
641 views

Origins of the term “distributed hash table”

I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came ...