Theoretical questions in Distributed Computing

learn more… | top users | synonyms (2)

0
votes
0answers
25 views

What is the resolution of the apparent contradiction in the Practical Byzantine Fault Tolerance paper?

This question refers to the paper by Miguel Castro and Barbara Liskov. On Page 4, the fourth paragraph of 4.2, it says "the primary... multicasts a pre-prepare message with m piggybacked to all the ...
10
votes
1answer
157 views

Correctness proofs of classic Paxos and Fast Paxos

I am reading the "Fast Paxos" paper by Leslie Lamport and get stuck with the correctness proofs of both classic Paxos and Fast Paxos. For consistency, the value $v$ picked by the coordinator in phase ...
5
votes
0answers
108 views

What is the significance of regarding the mutual exclusion problem as a problem of physics?

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote Most computer scientists regard synchronization problems, such ...
2
votes
1answer
84 views

Concurrent data structures vs. Distributed data structures

In the context of multi-processor/multi-threaded systems, there are plenty of well-studied concurrent data structures, including stacks, queues, linked lists, etc. Here is an excellent survey on ...
7
votes
3answers
177 views

Job scheduling: minimizing number of reads

Consider the following scheduling problem: input: set of computations $C = \{c_1, ..., c_n\}$ set of computing nodes $P = \{p_1, ..., p_n\}$ Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ ...
3
votes
0answers
143 views

Election algorithm with unreliable messages and a certain timestamp

I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows: Messages are sent unreliably with an at-most-once sending Nodes are ...
3
votes
2answers
174 views

What does it mean for CvRDT replicas to transmit their state “infinitely often”?

In Shapiro et al.'s SSS '11 paper on Conflict-Free Replicated Data Types for eventual consistency of distributed replicated objects, they describe a system model in which replicas transmit their state ...
2
votes
0answers
104 views

Totally ordered multicast with Lamport timestamps

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 ...
2
votes
0answers
34 views

Are the sets of executions of data-race free programs equal, when run on causal memory and on sequentially consistent memory respectively?

In the paper "Causal Memory: Definitions, Implementations, and Programming (Distributed Computing [DC] 1995)", the authors present a formal definition of causal memory, an abstraction of distributed ...
10
votes
2answers
297 views

Why is linearizability a safety property and why are safety properties closed sets?

In Chapter 13 "Atomic Objects" of the book "Distributed Algorithms" by Nancy Lynch, linearizability (also known as atomicity) is proved to be a safety property. That is to say, its corresponding trace ...
1
vote
0answers
25 views

What is the staleness in this execution of the $k$-atomic multi-writer register construction from $k$-atomic single-writer ones?

Background: $K$-atomicity is a consistency condition meaning that a read operation can return one of the values written by the last $k$ preceding writes in an order consistent with real time. It is a ...
8
votes
1answer
148 views

What is the advantage of designing deterministic distributed algorithms?

Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem. Paxos is deterministic in the sense that given the ...
1
vote
1answer
55 views

2PC with URBcast

Two phase commitment can be used for distributed transaction commitment. But it is consider as a blocking protocol when we used it with a best effort broadcast (BEBcast). My first question is, can we ...
1
vote
0answers
49 views

Atomic snapshot algorithms on tree-structured shared registers

Background: Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (*scanned) in its entirety. The Gang of Six algorithm ...
0
votes
0answers
27 views

synchronization problem in complex networks

What is the time and communication complexity of synchronizing clocks on a random graph of N vertices, whose degrees are distributed according to a power-law?
1
vote
1answer
60 views

Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm?

Backgroud I am reading Chapter 10 ``Fault-Tolerant Simulations of Read/Write Objects'' of the Book Distributed Computing (by Hagit Attiya & Jennifer Welch). Specifically, in section 10.2.3, it ...
4
votes
1answer
305 views

Is This Scheduling Problem NP-Hard?

The scheduling problem (arising from distributed computing) is defined as a decision problem as follows: Instance: A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, ...
1
vote
1answer
170 views

How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

I am trying to motivate, define, and implement $K$-atomic snapshot object. To this aim, I first give some basic definitions on atomic snapshot object and $K$-atomic object. Then, I will give my ...
3
votes
1answer
200 views

Termination of the Bellman-Ford algorithm in asynchronous distributed model

I'm looking for an algorithm to compute the BFS tree of a graph rooted in the leader processor $r$ in the asynchronous distributed model. The only requirement is $O(D)$ time complexity, where $D$ ...
1
vote
1answer
75 views

bounds in centralized and distributed

If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?
9
votes
1answer
254 views

Is linearizability equivalent to consensus problem?

In the introduction of this paper Eventually Linearizable Shared Objects (PODC'10), the authors have presented the following statement without references: Linearizability, however, can be achieved ...
2
votes
1answer
149 views

Distributed file storage system - theoretical approaches

What are the main theoretical approaches to a distributed file storage system that allows files to be stored across a network of nodes, assuring their availability in case a node randomly loses ...
0
votes
0answers
160 views

Order of operations in 2 and 3 phase atomic commit protocols

I am currently reading through this http://research.microsoft.com/en-us/people/philbe/chapter7.pdf chapter about distributed recovery. The chapter focuses on 2 phase atomic commit (2PC) and 3 phase ...
13
votes
1answer
374 views

Is there a list of canonical problems in distributed systems?

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 ...
7
votes
1answer
185 views

Who said: “There is no central arbiter of truth in open distributed systems.”

Can anyone give me a reference to the origin of the statement "There is no central arbiter of truth in open distributed systems." Possibly it was Carl Hewitt in "The Challenge of Open Systems" Byte ...
3
votes
1answer
267 views

How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

The following question was first presented in MATHEMATICS of StackExchange. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such ...
5
votes
0answers
202 views

Distributed algorithms on sets

Given a connected arbitrary network $G = (V,E)$, where $V$ is a set of nodes (processors) and $E$ is the set of edges between the nodes. Each node $v _i$ is assigned a non-empty set $S(v _i)$, where ...
10
votes
2answers
2k views

Why is the consensus problem so important in distributed computing?

In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One ...
1
vote
3answers
430 views

Does mathematical model for conccurent computations exist?

Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time? If yes, how are the concurrent computations ...
3
votes
1answer
101 views

Lower bound for orienting an asynchronous ring?

We require a lower message complexity bound of an asynchronous distributed algorithm that do the following: Given a undirected ring, with $n$ vertices, we want to let each node direct its edges to ...
-3
votes
2answers
205 views

Model checking Paxos

I have implemented consensus algorithm (based on Paxos). I have added some random test cases and it seems fine. To be sure, I want to do testing via model checking. I couldn't find a correct article ...
8
votes
0answers
251 views

Existence of “colouring matrices” — a generalisation

This is a generalisation of the following post: Existence of "colouring matrices". As the base case turned out to be fairly straightforward (in essence, precisely equal to the existence of Sperner ...
9
votes
2answers
183 views

Existence of “colouring matrices”

Edit: there is now a follow-up question related to this post. Definitions Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$. A $c \times c$ matrix $M = (m_{i,j})$ is said to ...
4
votes
2answers
446 views

Efficient synchronization of two instances of an ordered list

What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move ...
6
votes
1answer
140 views

Minimal bandwidth required to synchronize two sets of values

We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the ...
4
votes
3answers
363 views

How to understand the “Availability” of the CAP theorem?

As we know, in the CAP theorem, "A" means "Availability". On wikipedia, the explanation of "Availability" is: Availability: a guarantee that every request receives a response about whether it ...
0
votes
1answer
181 views

FloodSet in general networks

I would like to ask how could someone modify FloodSet algorithm to work in a general network, where process failures happen..Is it possible for it to work if a "crucial" [1] failure happens? [1]: As ...
5
votes
1answer
114 views

Honest Majority unconditional coinflipping without private channels

All communication is assumed to be by the parties taking turns making authenticated broadcasts. Is there a way for $n$ parties, each with access to ideal local randomness, to jointly choose ...
8
votes
1answer
2k views

Major unsolved problems in distributed systems?

Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain. Something like membership protocols, data ...
5
votes
1answer
196 views

Average message complexity for the election problem on graphs

I am currently studying the election problem in distributed algorithms. There, I stumpled over one approach to implement a Chang-Roberts-like message extinction algorithm on graphs without requiring a ...
6
votes
1answer
162 views

O(N) leader election on torus with orientation and non-positional identity

I'm really confused by this. Apparently there is a deterministic algorithm that does leader election on a torus with orientation and non-positional identity using only O(N) messages. I'm unable to ...
12
votes
3answers
485 views

Infinitely large but locally finite computation problems

This question is inspired by a comment Jukka Suomela made on another question. What are examples of infinitely large but locally finite computation problems (and algorithms)? In other words, ...
-2
votes
1answer
570 views

Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...
10
votes
1answer
309 views

Regular high-girth graph with a “locally uniform” total order on nodes

Definitions Let $\epsilon > 0$ and let $d$, $r$, and $g$ be positive integers (with $g > 2r+1$). Let $G = (V,E)$ be a simple, $d$-regular, undirected, finite graph with girth at least $g$. Let ...
-3
votes
1answer
185 views

How can you tell between what is a “distributed” system versus “grid” computing versus “cluster” computing? [closed]

These terms seem to get thrown around rather vaguely, in my opinion, and was wondering if there were some hard-lined facts about what accounts for which category in these fields. If there aren't any, ...
10
votes
3answers
378 views

Efficient DAG comparison over a network

In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in ...
3
votes
1answer
353 views

What is “distributed computing” as a field of computer science?

I think it's field that studies distributed systems as described at http://en.wikipedia.org/wiki/Distributed_computing. There are distributed systems such as clusters and grids on top of this field. ...
12
votes
2answers
483 views

Decentralized algorithm for determining influential nodes in social networks

In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social ...
-2
votes
1answer
132 views

How to check if an algorithm in a distributed system worked within restraints?

I want to design a system in which a program is sent along with data and then it answers with the result. Is redundancy a must in this situation to check for correctness of the processed data? What is ...
2
votes
0answers
332 views

On the Bakery Mutual exclusion Algorithm

Lamport's Bakery Algorithm is one of the most elegant algorithms for mutual exclusion. The beauty of it is that it works even when the underlying system only provides a weak form of registers called ...