14

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) matching upper and lower bounds for the distributed time complexity of graph problems. For example, for many optimisation problems tight bounds are known. However,...


10

I will answer this from the perspective of distributed graph algorithms (distributed algorithms that solve a graph problem related to the structure of the communication network). Here are some non-obvious reasons for designing deterministic distributed algorithms in this setting: Subroutines in randomised algorithms. On p. 12–13 of these slides, Elkin ...


10

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 steps? You're looking at an instance of strong induction. In simple induction you assume the property holds for $n=m$ and prove it holds for $n=m+1$. In strong ...


9

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 distributed and geo-replicated databases. In order to execute transactions efficiently, such mechanisms can provide weaker guarantees than serialisability, which ...


9

Is there a set of canonical distributed systems problems from which all the possible distributed system problems can be reduced to? I'm unaware of such a published list of problems. Keep in mind that there are many different (and somewhat incomparable) models in distributed computing, ranging from the "benign" synchronous (fault-free) model where nodes ...


8

What are the advantages of linearizability as a safety property? Are there some results based on this fact in the literature? Suppose that you've implemented a shared memory machine $M$ that only satisfies eventual linearization, defined as follows: in every run $\alpha$ of $M$, there exists some point in time $T_\alpha$, such that linearization holds from ...


7

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 herein. The optimal time complexity remains an open problem. Concerning message complexity, As far as message complexity, although the asymptotically tight ...


6

Regarding your first question - safety properties are, in a way, the "easiest" properties to handle, with respect to problems such as model-checking and synthesis. The basic reason for this is that in the automata-theoretic approach to formal methods, reasoning about safety properties reduces to reasoning about finite traces, which is easier than the ...


6

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$ clauses, first build a variable assignment gadget like in the figure below (thanks to @Jukka for the clarifications, the graph drawing style, and the hint for the ...


5

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 system we can use it to linearize actions on shared objects and obtain linearizability for shared objects. For simplicity, how many problems can you think of ...


5

I'm not aware of a general rule to convert centralized bounds to the distributed setting. In the distributed setting, local computation is given for free but the difficulty lies in breaking the symmetry - a node needs to accumulate enough information about it's neighborhood to make a decision about being part of the output set, e.g. being in the MIS. (Taking ...


5

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 studies concurrency models with a particular focus, namely how information is exchanged for coordination.


4

This is a possible reduction from 3-partition which is strongly NP-complete. Given a set $A = \{a_1,a_2,...,a_{3m}\}$ of $3m$ positibe integers, and a target sum $B$. The basic idea is simple: if we found a read sequence like $Rx1\; Rx2\; Rx1$, even if the last write of $x$ before the sequence was a $Wx2$, the first $Rx1$ forces to "use" another $Wx2$ to ...


4

The thing you get wrong is "we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes." We don't know that, and in fact it is wrong. What the quote from the JACM95 paper shows is that single-writer multi-reader registers can be implemented using message passing. And only this ...


4

A simple approach to achieve reliability and fast lookup in a "well connected" network $G$ is to replicate each file $f$ on a set $V_f$ of $\Theta(\sqrt{n}\log n)$ nodes and use random walks to efficiently find members of $V_f$. When searching for a file $f$, we start $c\sqrt{n}\in \Theta(\sqrt{n})$ random walks of length $\tau$ from some particular node, ...


4

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 more of an applied slant but the key questions listed inevitably lead to theoretical areas. The Kiloscale Problem: Any workflow with sufficient concurrency ...


4

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 Distributed Computation is Communication Expensive" http://arxiv.org/abs/1304.4636 See also this work for closely related models: Klauck et al.: "Distributed ...


3

You can find a formal model and proof of Paxos and Byzantine Paxos written by L. Lamport et al at http://research.microsoft.com/en-us/um/people/lamport/tla/byzpaxos.html. The model can be checked using the TLA+ toolbox. Notice that the author of the Paxos algorithm, the formal model above, and even the TLA+ modeling language is the same person:)


3

For synchronizing from a master list to a slave list, it looks like a fellow named Michael Heyeck has a good, O(n) solution to this problem. Check out that blog post for an explanation and some code. Perhaps this is a good starting point to generalize to a two-way sync. Essentially, the solution tracks both the master and slave lists in a single pass, ...


3

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 = on which blue line we place each node = when to schedule each job costs = orange numbers = number of predecessors with different labels Left = simple greedy ...


3

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 computability power of shared objects in distributed systems, which includes registers.


3

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 this end, it first decomposes SI into four properties: Decomposition theorem: $SI = ACA \cap SCONS \cap MON \cap WCF$ where, $ACA$: avoiding cascading aborts;...


3

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 face, are handling dynamic changes, implementing a scalable design, and being fault-tolerant. This includes finding answers to questions such as: How can we ...


3

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 disjoint supports, so that the training sample can be nearly uninformative regarding the test performance. That having been said, there is a body of research ...


2

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 problem for networks of known size. If the size is unknown, then this minimum number is f+2. More precisely, we show a deterministic polynomial algorithm that ...


2

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 the order of "what we know, what we want to prove, and how to prove". Hope it helps. What we know: Base case: Some proposal with number $m$ and value $v$ is ...


2

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 order to be a superset of session order: $$\text{PRAM} \triangleq so \subseteq vis.$$ Thus, the offending arrow in your diagram, from $w(x)0$ to $r(x)0$, is ...


2

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 view makes it possible to focus on the inherent difficulties of the distributed aspects. In such cases, lower bounds related to classical (i.e. sequential) ...


1

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 here means depends on the context of the problem being solved), it is possible that an unscheduled interrupt occurs that pauses this communication and allows a ...


1

I found a reduction from the Partition Problem to a modified version of the proposed problem. Partition Problem (Optimization) input: set of integers S output: partition of S into S1 and S1 such that the difference of the sums of S1 and S2 is minimized: $$\lvert\sum_{s\in S1}s - \sum_{s\in S2}s\lvert.$$ This problem is NP-hard. Level Assignment Problem (...


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