Tagged Questions

Theoretical questions in Distributed Computing

learn more… | top users | synonyms (2)

1
vote
1answer
52 views

The proof of P2b in Paxos made simple

I am reading Paxos Made Simple. I am quite confused about the proof of P2b. It said We would make the proof easier by using induction on n, so we can prove that proposal number n has value v under ...
-3
votes
1answer
108 views

What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
0
votes
0answers
28 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 ...
11
votes
1answer
181 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
109 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 ...
3
votes
1answer
92 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
145 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
178 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
107 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 ...
11
votes
2answers
302 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
26 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 ...
9
votes
1answer
159 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
56 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 ...
2
votes
0answers
53 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 ...
1
vote
1answer
67 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
307 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
171 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
209 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$ ...
2
votes
1answer
78 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
262 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 ...
3
votes
1answer
154 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
391 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
189 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
270 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
204 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
439 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 ...
4
votes
1answer
104 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
210 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 ...
5
votes
2answers
468 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
365 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
187 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
115 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
197 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
164 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 ...
13
votes
3answers
487 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
573 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
311 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, ...
11
votes
3answers
382 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
358 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
487 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 ...