We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [dc.distributed-comp]

Theoretical questions in Distributed Computing

Filter by
Sorted by
Tagged with
41
votes
4answers
2k views

Why have we not been able to develop a unified complexity theory of distributed computing?

The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed ...
13
votes
1answer
923 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 ...
14
votes
4answers
572 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, what ...
30
votes
10answers
1k views

Current parallel models for computation

The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s. Are these areas still active in terms of ...
13
votes
2answers
557 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 ...
4
votes
1answer
378 views

Modern distributed computing book

Lynch's Distributed Algorithms book is a classic but it is from 1996 and rather out of date. Are there any recent distributed computing books that can be used as textbooks for a graduate distributed ...
9
votes
2answers
193 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 be ...
4
votes
1answer
414 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, p_{n-...
8
votes
0answers
256 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 ...
5
votes
1answer
180 views

Confusion about a formal definition of PRAM consistency

I am reading the paper "Consistency in Non-Transactional Distributed Storage Systems" by Paolo Viotti and Marko Vukolić. The authors provide a comprehensive survey of various consistency semantics ...
3
votes
1answer
425 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. ...
2
votes
1answer
218 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
0answers
238 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 ...
-2
votes
1answer
733 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 ...