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 ...
Kaveh's user avatar
  • 21.6k
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 ...
gasche's user avatar
  • 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 ...
Aryeh's user avatar
  • 10.5k
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 ...
Arnaud Casteigts's 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 ...
Bjørn Kjos-Hanssen's user avatar
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 ...
Corbin's user avatar
  • 271
1 vote

Sequential idempotence

This sounds a bit like absorption. But I'm not quite sure this is exactly what you need.
Matthias's user avatar
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 ...
J..y B..y's user avatar
  • 2,776
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., "...
Dmitry's user avatar
  • 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 ...
R B's user avatar
  • 9,448
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$...
Neal Young's user avatar
  • 10.8k
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 ...
Peter's user avatar
  • 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 ...
ivcha's user avatar
  • 186

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