# Tag Info

### 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) ...
• 11.3k
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 ...
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 ...

### 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 ...
• 2,319

### 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$ ...
• 22.3k

### 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 ...
• 21.3k

### 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 ...
• 1,910

### 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 ...
• 10.8k

### 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 ...
• 11.3k
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 ...
• 10.1k
Accepted

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 ...
• 1,241
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 ...
• 2,319

### 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 = ...
• 11.3k
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 ...
• 1,241

### 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 ...
• 243
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 ...
• 1,241

### 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 ...
• 2,319
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 ...

### 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 ...
• 4,400
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., "...
• 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 ...
• 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$...
• 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 ...
• 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 ...
• 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.
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,...
• 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 ...
• 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 ...
• 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 ...
• 2,319
1 vote
Accepted