Questions tagged [dc.distributed-comp]
Theoretical questions in Distributed Computing
108
questions
45
votes
4
answers
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 ...
- 655
29
votes
10
answers
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 ...
- 746
27
votes
4
answers
10k
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 ...
- 457
23
votes
1
answer
695
views
Estimating a percentile among distributed nodes without revealing values
I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it.
Problem: Suppose a list of N numbers is shared among a set of participants ...
ryan
19
votes
4
answers
11k
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 ...
- 2,329
16
votes
0
answers
169
views
Is it possible to boost the error probability of a Consensus protocol over dynamic network?
Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
- 211
14
votes
5
answers
2k
views
Processor failures in distributed computing that are not crash or Byzantine
There are two main types of processor failures in distributed computing models:
(1) Crash failures: a processor stops, and never starts again.
(2) Byzantine failures: processors behave adversarially, ...
- 6,994
14
votes
4
answers
636
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 ...
- 6,994
14
votes
1
answer
859
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 ...
13
votes
2
answers
273
views
complexity of randomized gossiping
The gossiping problem in distributed systems is the following. We have a graph $G$ with $n$ vertices. Each vertex $v$ has a message $m_v$ that must be send to all nodes.
Now, my question is in the ...
- 3,063
13
votes
1
answer
1k
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 ...
- 2,329
13
votes
2
answers
585
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 ...
- 203
12
votes
5
answers
1k
views
Distributed Turing Machine?
I'm a master student focused on distributed systems but also interested on theoretical computer science. I was wondering if there is a formal representation of a distributed system on top of a turing ...
11
votes
3
answers
590
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 ...
- 211
11
votes
1
answer
266
views
What algorithms/reading matter would you recommend on resolving transactions / read-write locks?
A simplified classical database transaction can be viewed as:
reading M items
performing some calculation based on those reads
writing some N results based on these calculations, which may include ...
- 211
10
votes
2
answers
650
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 ...
- 2,329
10
votes
2
answers
507
views
Limits on lock-free collections?
David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way.
This ...
- 334
10
votes
3
answers
589
views
Papers on fault handling in distributed systems
What papers on handling errors in distributed systems do you recommend?
- 696
10
votes
1
answer
573
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 ...
- 201
10
votes
2
answers
246
views
Shuffling of tokens on a graph using local swaps
Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.
I want to uniformly shuffle the tokens amongst the graph using only local ...
- 3,063
10
votes
1
answer
640
views
What are the major research issues in distributed transactions?
Background: Transaction processing has been a traditional research topic in database theory.
Nowadays distributed transactions are popularized by the large-scale distributed storage systems which ...
- 2,329
10
votes
1
answer
362
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 $\...
- 11.5k
9
votes
2
answers
223
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 ...
- 11.5k
9
votes
1
answer
788
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,329
8
votes
2
answers
3k
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 ...
- 181
8
votes
0
answers
261
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 ...
- 11.5k
7
votes
3
answers
228
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)$ ...
- 247
7
votes
1
answer
247
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 ...
- 113
7
votes
1
answer
256
views
Is it possible to model maximization in a petri net without using inhibitor arcs?
Creating a petri-net that models the minimum function is quite simple:
...
- 173
7
votes
1
answer
145
views
Confusions about the technique for verifying implementations of linearizable objects in [Herlihy and Wing, 1990]
In Section 4.3.2 entitled "Proof Method" of
Herlihy and Wing, "Linearizability: A Correctness Condition for Concurrent Objects", 1990
the authors describe the technique for
verifying ...
- 2,329
6
votes
4
answers
1k
views
Distributed Elections using Logical Clocks (hints and tips)
I need to implement one of the logical clock algorithms (described here), to allow me to coordinate an election protocol for a distributed system. I'm struggling to work out how I might go about using ...
- 243
6
votes
1
answer
157
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 ...
- 9,269
6
votes
1
answer
277
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 ...
- 161
6
votes
0
answers
124
views
Fair and "robust" fallback permutations
The following is a fun problem we stumbled into today.
We have work we wish to distribute on machines $1..n$. Each piece of work is given a list of machines to try, in order. If any machine fails, ...
- 1,379
5
votes
2
answers
899
views
How is rebalancing of DHTs handled in case of failure or addition of new node?
I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say:
A new node is added to the cluster (since all the nodes are full) then the whole ...
- 457
5
votes
1
answer
125
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 a ...
user6973
5
votes
1
answer
239
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 ...
- 2,329
5
votes
1
answer
249
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 ...
- 153
5
votes
1
answer
713
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 ...
- 4,041
5
votes
0
answers
140
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,329
5
votes
0
answers
229
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 $\...
- 644
4
votes
3
answers
353
views
How can I model this usage scenario mathematically?
I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system.
The system behaves as follows:
clients periodically issue multi-cast packets ...
- 153
4
votes
3
answers
473
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 was ...
- 141
4
votes
1
answer
202
views
Has ping based failure detector 'strong completeness' and 'weak accuracy'?
I was reading 'Unreliable Failure Detectors for Reliable Distributed Systems' (PDF) and I was wondering if ping (with increasing timeouts in case of failure) is in class S of failure detectors:
...
- 696
4
votes
1
answer
487
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-...
- 2,329
4
votes
1
answer
125
views
"Learning" when test and train distributions don't match
We know that the theory of PAC-learning is distribution-free, i.e. assuming that the test and train distributions are the same, we have guarantees on learning the hypothesis.
Question: what if the ...
- 749
4
votes
1
answer
160
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 ...
- 644
4
votes
3
answers
549
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 ...
- 323
4
votes
0
answers
146
views
2-hop distributed coloring in the CONGEST model
Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$.
A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
- 9,448
3
votes
5
answers
886
views
How is Real-Time Computing defined?
How is real-time computing defined in theoretical computer science (e.g. complexity theory)? Are there complexity theoretic models designed to capture the real-time computation?
- 41