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

learn more… | top users | synonyms (1)

2
votes
1answer
26 views

Counting the nodes in a network in a distributed way

There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters). One of the nodes, say $s$, wants to know $n$. How can it do ...
1
vote
1answer
15 views

Paxos: Instances, Rounds, Phases

In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a $prepare$ phase, and an $accept$ phase. An instance of Paxos can have multiple rounds. Can a round have multiple ...
2
votes
1answer
23 views

Paxos: Responding to Reordered Prepare Requests

In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a prepare request with: A promise never to again accept a proposal numbered less than n, and the proposal with the ...
1
vote
1answer
58 views

What is the size of a queue associated with a resource when the resource becomes a bottleneck?

In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the ...
4
votes
1answer
54 views

Does location transparency imply access transparency?

In distributed systems theory, I have found the definition that a distributed system requires, among others, location and access transparency. I was wondering if location transparency does not ...
2
votes
2answers
69 views

Linearizability and Serializability in context of Software Transactional Memory

I've been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general. At this ...
2
votes
0answers
42 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the ...
6
votes
2answers
68 views

Computer science fields that deal with peer-to-peer systems

I'm an undergraduate and am looking forward to becoming an academic; do the whole PhD stuff and start doing research. I'm interested in a variety of computer science related things but lately P2P ...
2
votes
1answer
50 views

Paxos: Accepting Proposals With Different Values and Consensus in Paxos

I have a number of questions about Paxos which I can't answer in full confidence from reading the paper (Paxos Made Simple). My questions are loosely based around the following quote: In Paxos, a ...
1
vote
1answer
30 views

How to make a “Secure by Design” client-server communication?

Is there a way to have a secure by design client-server communication in a sense that the server can check if the client is not a modified version? What I'd like to do is give the user access to both ...
2
votes
1answer
37 views

Residence time in multi server system

I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is: ...
4
votes
3answers
77 views

Happened-before and Causal order

I'm reading Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" and there's a detail that's bugging me. Lamport defines the "happened before" partial order, which I ...
6
votes
1answer
71 views

Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...
2
votes
1answer
104 views

Applications of Lamport's Distributed Mutual Exclusion algorithm

I'm trying to understand the relevance of the Lamport distributed mutual exclusion algorithm (or any of its variants), where a group of processes cooperate to gain exclusive access to a resource ...
3
votes
1answer
52 views

Confusion about example in Raft consensus paper

In part (c) of Figure 8 in this paper http://ramcloud.stanford.edu/raft.pdf, I am confused how S1 knows that the current term is 4 when it restarts and is elected leader. Here is the sequence as I ...
2
votes
1answer
70 views

How to interpret the execution of distributed computation from time-space diagram?

I'm following a course on Distributed Systems http://www.ict.kth.se/courses/ID2203/index.html and currently learning about asynchronous models. I can't seem to reconcile a given time-space diagram ...
1
vote
0answers
24 views

determining timeouts / retry attempts in distributed systems

Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution ...
2
votes
1answer
39 views

Difference between BSP model and synchronous round model in distributed computing

I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens: every node can send a message to ...
0
votes
1answer
68 views

Clock skew vs clock offset in the context of clock synchronization network protocols

In the context of clock synchronization among nodes of a network, what is clock offset and what is clock skew? Are these terms synonymous or is there a difference between them?
1
vote
0answers
37 views

Examples of real world graphs that are too big for a single commodity-type machine

I've been reading on distributed systems for processing on large graphs. The most prominent examples include Pregel (developed by Google) and Apache Giraph. Most of these systems argue their existence ...
0
votes
0answers
20 views

Graph Partition Across Cluster - Minimize Largest Matrix Size

I am writing some code for modeling semi-biologically realistic neural networks, which is to be run/distributed across nodes in a computer cluster. I begin with a very large adjacency matrix ...
1
vote
0answers
22 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
73 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 ...
5
votes
1answer
70 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
39 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
35 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
52 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
1answer
62 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
30 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
1answer
38 views

What is the correct term for “time to establish a connection” [on hold]

I don't remember what is the term for "time to establish a connection". For example in a smartphone, when I lost the wifi signal and the phone try to get mobile data connection it spends a bit of ...
0
votes
0answers
11 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
18 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
22 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
71 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
190 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?
2
votes
0answers
254 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
70 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 ...
5
votes
2answers
69 views

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

The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link ...
1
vote
1answer
111 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
59 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
113 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
34 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
28 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
49 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
48 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, ...
9
votes
1answer
128 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
36 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
69 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
64 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
86 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: ...