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
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
397 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
653 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 ...
27
votes
7answers
14k 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
860 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
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?
69
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
661 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 ...
4
votes
2answers
116 views

Message receipt verification in a cluster

At my current project I had a network problem come up for which I could not find a solution. In a peer-to-peer network I needed to send an action to all peers, and each peer was to act on it only if ...
6
votes
1answer
318 views

per-record timeline consistency vs. monotonic writes

It seems to me that the per-record timeline consistency as defined by Cooper et al. in "PNUTS: Yahoo!’s Hosted Data Serving Platform" mimics the (older?) definition of monotonic writes. From the paper:...
23
votes
1answer
4k views

How Does Populating Pastry's Routing Table Work?

I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify. Disclaimer: I'm not a computer science student. I've ...
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 ...
15
votes
1answer
820 views

All soldiers should shoot at the same time

When I was a student, I saw a problem in a digital systems/logic design textbook, about N soldiers standing in a row, and want to shoot at the same time. A more difficult version of the problem was ...
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 ...
63
votes
8answers
68k views

Distributed vs parallel computing

I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty ...
20
votes
1answer
2k views

distributed alpha beta pruning

I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see ...
20
votes
4answers
7k views

Measuring one way network latency

This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is ...
7
votes
1answer
427 views

Analyzing load balancing schemes to minimize overall execution time

Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given ...
39
votes
6answers
8k views

Clock synchronization in a network with asymmetric delays

Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want ...

1
3 4 5 6
7