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

learn more… | top users | synonyms (1)

3
votes
0answers
21 views

Visualization of Lamport's three-dimensional “space-time diagram” with introduced “tick lines”

In the third page (the third paragraph in the right column) of the paper "Time, Clocks, and the Ordering of Events in a Distributed System" by Leslie Lamport, it says that The reader may find it ...
0
votes
1answer
17 views

Emulation, interpreters and parallel execution

I'm interested in how software emulators of old game consoles work. These must consist of an interpreter for the machine language of the emulated processor. If I have understood correctly an ...
2
votes
0answers
11 views

How p2p search engines could prevent corruption of distributed index by malicious peers?

As a hobby I'm writing simple and primitive distributed web search engine and it occurred to me it currently has no protection against malicious peers trying to skew search results. Current ...
4
votes
0answers
32 views

Extend the causal memory implementation 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 ...
2
votes
1answer
36 views

In Paxos, what prevents multiple values from being chosen?

Say we have two proposers (P1, P2), one acceptor (A), and two learners (L1, L2). What would prevent this sequence of events from occurring? P1 initiates a round numbered 1. A agrees to participate, ...
7
votes
0answers
89 views

Can the end-to-end principle be formalized?

In the late 1990s, when I was in graduate school, the paper JH Saltzer; DP Reed; DD Clark: End-to-end arguments in system design. ACM Trans. Comput. Syst. 2(4):277-288, 1984. ...
-1
votes
1answer
28 views

TCP repeated acknowledgement

My professor has asked this (exam) question and it actually makes no sense to me: TCP offers a reliable, bidirectional byte stream over the best effort packet delivery in IP. For reliability, a ...
0
votes
1answer
49 views

Three phase commit : study case

Consider a group of five processors implementing three-phase commit protocol. During the execution of the protocol, the coordinator and one other process crash. Two of the remaining processes are ...
3
votes
3answers
52 views

Why can't every computation be expressed in the style of MapReduce?

What are the limitations of map reduce in the sense of the types of computations that they can express? Is Map Reduce "turning complete"? I have been told that map reduce only works on things that ...
2
votes
0answers
37 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: ...
-2
votes
1answer
68 views

MIS algorithm for Tree in O(log* n) time

I know Distributed Graph Coloring algorithm in O(log* n) which is given at P11: Vertex Coloring Same for Maximal Independent Set [MIS] they gave remark like algorithms exist in O(log* n) time at P70: ...
2
votes
1answer
28 views

Why does an acceptor send the highest numbered proposal with number less than n as a response to prepare(n) in paxos?

I was reading the Paxos notes from yale from the following link: http://pine.cs.yale.edu/pinewiki/Paxos Recall that Paxos is a distributed system algorithm with the goal that the processes ...
3
votes
0answers
122 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 ...
1
vote
0answers
44 views

What are the models of distributed storage systems in the literature?

To understand the effectiveness and/or efficiency of a protocol implemented in distributed storage systems, it is often desirable to evaluate it in a quantitative way under a hypothetical model. ...
1
vote
1answer
49 views

How does Paxos maintain the promise that future proposal will not break the current chosen value without knowing the future?

I was studying Paxos from: http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf and I was trying to understand page 4, specifically, the following paragraph: "To maintain the ...
3
votes
1answer
36 views

How do we make sure in Paxos that we don't propose a different value if a majority has formed?

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: ...
1
vote
0answers
56 views

What guarantees Paxos to converge (terminate)? (i.e. not run forever without a consensus)

I was studying Paxos from: http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf and was wondering, what guarantees Paxos to converge and not run forever without a ...
3
votes
0answers
59 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 ...
0
votes
1answer
67 views

Rational of why Paxos only issues new values if its value is the largest one in the majority that he can see?

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
1answer
43 views

What does it mean that numbers are “totally ordered”? (paxos made simple)

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 ...
2
votes
2answers
62 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: ...
1
vote
1answer
39 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 ...
4
votes
1answer
101 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
33 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
25 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
141 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
56 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
25 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
22 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
48 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
31 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 ...
2
votes
0answers
31 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 ...
1
vote
3answers
259 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
107 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
54 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 ...
5
votes
2answers
303 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 ...
2
votes
1answer
68 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 ...
6
votes
2answers
114 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
57 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
76 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
36 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
174 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. ...
2
votes
1answer
43 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 ...
7
votes
0answers
155 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 ...
2
votes
1answer
62 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
86 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 ...
6
votes
1answer
91 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
81 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
35 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
28 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 ...