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

learn more… | top users | synonyms (1)

1
vote
0answers
16 views

What mathmatical model shall be used for describing P2P processes interaction?

I am creating a distributed service system. It runs in the cloud on heterogeneous hardware. I am using C# .NET for business logic and C++ for different physics\chemical calculations. Having three ...
2
votes
1answer
40 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
1answer
30 views

Why do relational databases use 2PC for distributed transactions over the likes of Paxos?

Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case ...
1
vote
0answers
36 views

Find the size of the maximum cycle in a MPS

Consider the following problem to be solved in a distributed context: Find for each processor the size of the biggest cycle of which it is member. My algorithm is the following (for synchronous ...
0
votes
1answer
29 views

simple lower bound for constructing a Spanning tree

i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts ...
1
vote
0answers
42 views

computational and messages complexity equivalence between STP and Leader election

I'm doing a presentation for a distributed systems and networks course. I'm using the book "Design and Analysis of Distributed Algorithms", written by Nicola Santoro. This book contains the proof of ...
4
votes
0answers
34 views

Byzantine generals problem with signed messages (Lamport)

I have some trouble understanding Lamport's paper about the Byzantine generals problem when it comes to signed messages. He showed that, with signed messages, the number of generals must be at least ...
2
votes
1answer
21 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 ...
0
votes
0answers
10 views

Does Optimistic Concurrency per object imply Serializability if a transaction will never span multiple objects?

Given a system which provides: Optimistic concurrency control / versioning per object (using CAS - Check-and-Set) Transactions that never need to span more then a single object. Snapshot Isolation ...
5
votes
1answer
14 views

Proof of commonality of acceptors in majorities

In the Paxos consensus protocol, a fact that follows from its construction is "any two majority sets of acceptors will have at least one acceptor in common". This observation can be extended to any N ...
2
votes
0answers
20 views

Distributed push relabel with changing graph topology

There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. ...
3
votes
1answer
39 views

Lamport Timestamps: When to Update Counters

In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following: Each process $Pi$ increments $Ci$ between any two ...
0
votes
1answer
45 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?
1
vote
0answers
85 views

How are Distributed Snapshot algorithms (likes of Chandy Lamport) implemented in real world distributed systems? [closed]

Can anyone explain, how Distributed Snapshot algorithms ( Example: Chandy-Lamport are implemented in the context of modern distributed systems? Can you name an open source System implementation ...
1
vote
1answer
61 views

Determining on whether topology is a tree or a hypercube

Assume that the nodes know that the topology G is either a hypercube or a tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to ...
4
votes
0answers
32 views

Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

The well-known ABD algorithm in Sharing Memory Robustly in Message-Passing Systems can emulate atomic, single-writer multi-reader registers in message-passing systems, in the presence of processor or ...
1
vote
1answer
53 views

How are lamport clocks implemented in real world distributed systems?

Can anyone explain, how lamport clocks implementations are used in modern distributed systems? Can you name an open source package which implements this algorithm?
2
votes
1answer
54 views

What actually is the concept of transparency? Why not call it Abstraction?

I searched this over Google few times but ended up with articles on transparency rather than an answer. With relation to distributed database study(or distributed OS), what is the concept of ...
4
votes
1answer
64 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
29 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
1answer
25 views

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

As a hobby, I am writing a simple and primitive distributed web search engine. It occurred to me that it currently has no protection against malicious peers trying to skew the search results. The ...
4
votes
0answers
47 views

Extending the causal memory model 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
43 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
103 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
31 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 ...
1
vote
1answer
65 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
58 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 ...
1
vote
1answer
57 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
94 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: ...
1
vote
2answers
50 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
524 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
49 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. ...
0
votes
1answer
56 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 ...
2
votes
1answer
39 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: ...
0
votes
0answers
82 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 ...
2
votes
0answers
60 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 ...
-1
votes
1answer
78 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 ...
2
votes
1answer
51 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 ...
1
vote
2answers
65 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: ...
0
votes
1answer
66 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
109 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 ...
2
votes
1answer
36 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
27 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
195 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
62 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
29 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
24 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
62 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
33 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
41 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 ...