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 ...
- 21.5k
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 ...
- 2,040
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 ...
- 10.3k
3
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 ...
- 11.5k
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 ...
- 1,251
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 ...
- 2,329
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 ...
- 356
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 ...
- 4,475
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 ...
- 271
1
vote
Sequential idempotence
This sounds a bit like absorption. But I'm not quite sure this is exactly what you need.
- 61
1
vote
Selecting unique records from a large dataframe with many duplicate records
In the context of Theoretical Computer Science, there are various strategies to (quickly) select the unique elements of a list, mainly comparison based and value based.
Value based: If computing a ...
- 2,733
1
vote
Accepted
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., "...
- 201
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,438
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$...
- 9,595
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,251
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 ...
- 186
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,...
- 845
Only top scored, non community-wiki answers of a minimum length are eligible