Questions about the challenges of solving problems with multiple cooperating but separate agents.
3
votes
1answer
38 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 ...
4
votes
1answer
53 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 ...
4
votes
2answers
46 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
26 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
54 views
Is there a list of canonical problems in distributed systems? [closed]
Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about Solved Problems, Unsolved Problems and Non-Problems in Concurrency. The paper is easily readable, but ...
2
votes
0answers
18 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
1answer
52 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 ...
2
votes
1answer
78 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 ...
6
votes
1answer
135 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 ...
1
vote
0answers
82 views
Assumptions in Solving Leader Election Problem
There is a well known problem of Leader Election in the field of Distributed Programming.
The are few classes of algorithns designated for solving Leader Election problem. The largest class is the ...
2
votes
1answer
91 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 ...
1
vote
0answers
80 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
131 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
59 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 ...
2
votes
0answers
103 views
Time complexity for synchronizer
In the field of Synchronizers on Distributed algorithms exists two type of time complexities of synchronizer $\xi$. Where $\xi$ denotes any synchronizer.
$T_\text{pulse}(\xi) = \max \left \{ ...
0
votes
0answers
56 views
Bond energy and vertical partitioning to get a vertical fragmentation in distributed dbms
Can anybody please solve the following problem step-by-step with explanations, using bond energy and vertical partitioning to obtain a vertical fragmentation of the set of attributes.
I need to ...
2
votes
1answer
78 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. ...
0
votes
0answers
24 views
adjustment and tuning in database [closed]
"It is well known that design and development activity of any kind is an ongoing
process requiring constant monitoring and periodic adjustment and tuning."
What is adjustment and tuning in database ...
0
votes
0answers
34 views
In DDBMS, What meaning of corresponding sites?
The last step in the design process is the physical design, which maps the local conceptual schemas to the physical storage devices available at the corresponding sites.
What meaning of corresponding ...
0
votes
0answers
51 views
Top-Down Design Process in Distributed Databases
"There is a relationship between the conceptual design and the view design. In one
sense, the conceptual design can be interpreted as being an integration of user views.
Even though this view ...
-1
votes
1answer
51 views
How to repeat a mapreduce process? [closed]
How can I repeat the map and reduce process and feed the output of reduce into map function (in the next round)?
My second question is how to define a global variable with is accessible among all map ...
4
votes
1answer
63 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
55 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 ...
8
votes
2answers
156 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)?
3
votes
1answer
79 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
27 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 ...
0
votes
0answers
149 views
Final year project advice for Computer Science [closed]
I am thinking of something that would require extreme use of algorithms.
After some deliberation i am thought of making a search engine. I have searched the internet and the project seems fairly ...
6
votes
6answers
267 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 ...
1
vote
0answers
87 views
Object-based distributed Operating systems [closed]
Can any one explain how object-based technology used in distributed operating systems?
Also can any one suggest any learning resources (links, slideshows, e-books etc) to learn about Amoeba OS?
2
votes
1answer
145 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
35 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?
21
votes
4answers
778 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 ...
6
votes
1answer
172 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
66 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 ...
5
votes
1answer
66 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 ...
14
votes
1answer
297 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 ...
4
votes
0answers
27 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 ...
12
votes
1answer
360 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 ...
6
votes
0answers
41 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 ...
15
votes
3answers
2k 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 ...
9
votes
0answers
188 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 ...
10
votes
2answers
415 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 ...
4
votes
1answer
146 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 ...
24
votes
5answers
988 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 ...
