17

The paper you mention is important for 2 reasons: It shows that there is no asynchronous deterministic consensus algorithm that tolerates even a single crash fault. Note that in the synchronous setting,there is a deterministic algorithm that terminates in $f+1$ rounds when $\le f$ processes crash. It introduces bivalence and univalence of configurations (*),...


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

The construction is optimal in the sense that $\binom{2n}{n}+1 \leadsto n$ cannot hold. Indeed, it is easy to see that c-to-k coloring matrix exists if and only if there are c subsets A1, …, Ac of the set {1, …, k} such that no distinct i and j satisfy Ai ⊆ Aj. (For the “only if” direction, take Ai = R(M, i) for a c-to-k coloring matrix M. For the “if” ...


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 ...


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 ...


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 ...


8

The exact quotation seems to be: "Pluralism: There is no central arbiter of truth in the system." See: http://archive.org/stream/byte-magazine-1985-04/1985_04_BYTE_10-04_Artificial_Intelligence#page/n237/mode/2up (p. 239, 2nd bullet point.)


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 ...


7

It shows that there are no fault-tolerant deterministic algorithm. Quite a strong theoretical result, which forces designers to deal differently with fault-tolerance, some of which are synchronization and randomization. Comment: In my opinion, synchronization is an additional assumption of the system that are hardly found in practical applications. For ...


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 ...


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

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

From what i know, The BSP and LogP models are used today for distributed algorithms. Also, since GPU computing, the PRAM as become again popular, however one should include the memory hierarchies in the analysis. You can check the UPMH model (Uniform Parallel memory hierarchy) which complements nicely to PRAM. B. Alpern, L. Carter, E. Feig, and T. Selker. ...


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

As already suggested above, process algebra or process calculus is the place to start. Quoting freely from the respective Wikipedia page, History In the first half of the 20th century, various formalisms were proposed to capture the informal concept of a computable function, with μ-recursive functions, Turing Machines and the lambda calculus ...


3

The idea is growing territories. That is, a candidate broadcast to neighbors that are $\alpha^i$ away in iterations. The trick is in the analysis! (so it s not really clear) -- by getting to know the worst case of candidates, and the number of messages they send + setting $\alpha$ to a certain constant - we get $O(n)$ The solution can be found in N. ...


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

Your question is mixing two somewhat orthogonal interpretations of the term "Availability". The "reliability theory"/"engineering" interpretation, where availability is basically the ratio of time the system is not failed. The "distributed computing" interpretation, which is centered around the idea that "every ...


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

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

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

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

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 ...


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