14 votes

Major unsolved problems in distributed systems?

The distributed time complexity of numerous graph problems is still an open question. In general, distributed graph algorithms is an area in which we would expect to have (at least asymptotically) ...
user avatar
10 votes
Accepted

Correctness proofs of classic Paxos and Fast Paxos

Why can we assume that property CP held when acceptor a0 voted for v in round k? It seems that we are using mathematical induction, therefore, what are the basis, inductive hypothesis, and inductive ...
user avatar
9 votes
Accepted

What are the major research issues in distributed transactions?

There are many research areas both in the theory and practice of distributed databases. One of the main practical challenges is that of implementing efficient concurrency control mechanisms for ...
user avatar
7 votes

Major unsolved problems in distributed systems?

Open problems on "Distributed Algorithms for Minimum Spanning Trees (MST)": (listed in [1]) Concerning time complexity, Near time optimal algorithms and lower bounds appear in [2] and references ...
user avatar
  • 2,319
6 votes

Job scheduling: minimizing number of reads

After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT. Given a 3SAT formula with $x_1,...,x_n$ variables and $C_1,...,C_m$ ...
user avatar
6 votes

Why is the consensus problem so important in distributed computing?

One reason consensus problems are important is that they are very simple and they are kind of universal problems for distributed computing systems. If we can solve consensus in an async distributed ...
user avatar
  • 21.3k
5 votes

Can concurrency models be compared in terms of some metrics?

There are no metrics, but an excellent discussion of many concurrency models, in Tony Garnock-Jones PhD thesis. See the (HTML version of the) chapter "Approaches to coordination". This ...
user avatar
  • 1,910
4 votes

Major unsolved problems in distributed systems?

see also (more recently) a slideshow "Unsolved Computer Science Problems in Distributed Computing" from 2012 by Notre Dame researcher Douglas Thain who leads their cooperative computing lab. it has ...
user avatar
  • 10.8k
4 votes

Does such model exists?

The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"): Woodruff & Zhang: "When ...
user avatar
3 votes
Accepted

"Learning" when test and train distributions don't match

In general, the results are pretty strongly negative --- fairly strong assumptions are needed for something like this to work. As an extreme case, suppose that training and testing distributions have ...
user avatar
  • 10.1k
3 votes
Accepted

Results about computability power or limitations of shared read/write registers

You might want to look at the work of Gadi Taubenfeld. Many of his papers deal with impacts of different progress conditions such as (generalized) wait-freedom or obstruction-freedom on the ...
user avatar
  • 1,241
3 votes
Accepted

Lower bounds and impossibility results for distributed transactions

The arXiv paper "Non-Monotonic Snapshot Isolation" [1] proves several impossibility theorems demonstrating that SI (Snapshot Isolation) and GPR (Genuine Partial Replication) are incompatible. To ...
user avatar
  • 2,319
3 votes

Job scheduling: minimizing number of reads

This is a non-answer, but it might help to understand the question (assuming that I understood it correctly). Here is a simple but slightly non-trivial example: Here: input = black graph output = ...
user avatar
3 votes
Accepted

Concurrent data structures vs. Distributed data structures

What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)? Some important challenges that practically all distributed data structures ...
user avatar
  • 1,241
2 votes

What is "distributed computing" as a field of computer science?

Computer science studies "computers", whatever those are. Distributed computing, as a subfield, studies how individual computers behave when they are one of many computers which ...
user avatar
  • 243
2 votes
Accepted

What do these lower bounds really mean?

Note that the paper considers strongly Byzantine agents and weakly Byzantine agents. From the abstract: For weakly Byzantine agents, we show that any number of good agents permits solving the ...
user avatar
  • 1,241
2 votes

Paxos made simple, invariant P2c

We prove it ($P2^c \implies P2^b$) by strong induction (wiki). This proof has actually been given in the "Paxos Made Simple" paper (see the arguments between $P2^b$ and $P2^c$). I re-organize it in ...
user avatar
  • 2,319
2 votes
Accepted

Sequential vs Distributed algo question

There are several possible ways to answer this question. On the one hand, it is often assumed in distributed computing that the nodes have unbounded local computational power, because this point of ...
user avatar
2 votes

Confusion about a formal definition of PRAM consistency

When they define PRAM (page 11 of the arxiv preprint) they actually state that vis is a partial order (in particular, transitive): We define PRAM consistency by requiring the visibility partial ...
user avatar
1 vote

Lipschitz composable compressor

It turns out that there is a simple answer: $O(k)$-composable $\frac kd$ compressor (in expectation) just returns $k$ random coordinates. The proof is trivial and can be found in Stich et al., "...
user avatar
  • 190
1 vote

Complexity of distributively verifying that the diameter is small

There is an $O(k)$ rounds algorithm for distinguishing between graphs of diameter at most $k$ and those with a diameter larger than $2k$. This works in two stages: First, each vertex broadcasts the ...
user avatar
  • 9,378
1 vote
Accepted

Does the following 2-rounds distributed algorithm approximates a maximal matching well?

No. For the following graph the expected size of the generated matching is $O(\sqrt n)$, but any maximal matching has size $\Theta(n)$. The graph consists of a $k$-vertex core $C$ and a matching $M_0$...
user avatar
  • 8,273
1 vote

Why do timeouts require synchronized clocks?

Note that the authors also assume the following: Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processesor about ...
user avatar
  • 1,241
1 vote
Accepted

Distributed Consistency using Quorum approach

The idea behind implementing consistency with a quorum is to maintain consistency in one group (that contains the majority of replicas) and forcing, by construction, that reads and writes cannot ...
user avatar
  • 188
1 vote

Modern distributed computing book

You can refer Roger Wattenhofer's Lecture note on PODC. Here I mentioned some other courses on distributed algorithms.
user avatar
1 vote

Confusions about the technique for verifying implementations of linearizable objects in [Herlihy and Wing, 1990]

Herlihy and Wing write on p. 477: In conclusion, the rep invariant $\mathbf{I}$ must be continually satisfied and the abstraction function continually defined, not only between abstract operations,...
user avatar
  • 800
1 vote

What does the contention-free communication assumption really mean in the context of DAG scheduling?

Not my field of expertise, but I think this is a relaxation in comparison with real-life scenarios. In actual systems, once a connection has been established and a "packet" has been sent (what packet ...
user avatar
  • 3,741
1 vote

State of the art algorithms for community detection in graphs

There's a recent paper [1] on dense subgraph (i.e. community) detection in the context of distributed computing. In [1], each node of the graph represents an operating entity (i.e. runs an instance ...
user avatar
  • 1,241
1 vote

Proof of causal multicast algorithm?

Basically you have been mislead by the errors in the proof in the edition of the paper you are referring to. Please refer to the published edition on "Distributed Computing'1995". There's almost ...
user avatar
  • 2,319
1 vote
Accepted

The proof of P2b in Paxos made simple

Note: I have had a similar question about the correctness proof of Paxos and Fast Paxos before and posted it here. Wish the excellent answer to it be helpful to you. A few words about this paper: ...
user avatar
  • 2,319

Only top scored, non community-wiki answers of a minimum length are eligible