# Tag Info

28

See, for instance, Eight open problems in distributed computing.

18

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 (*),...

16

A single Turing machine can simulate a network of Turing machines and all communication between them (if you prefer to think about real computers, you could simulate/virtualize several computers on one computer). So whatever a network of TMs can compute, a single TM can compute, too.

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

13

Just to give some ideas of what is possible (but somewhat non-trivial), here is one example: a distributed algorithm that finds a maximal edge packing on a bounded-degree graph. Problem definition Given a simple undirected graph $G = (V,E)$, an edge packing (or fractional matching) associates a weight $w(e)$ with each edge $e \in E$ such that for each node ...

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

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

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

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

This appears to be known as the "set reconciliation" problem. The key paper appears to be Minsky & Trachtenberg, "Set Reconciliation With Nearly Optimal Communication Complexity", IEEE Transactions on Information Theory (2003). Also, here is some subsequent work on this problem by the same authors: "Practical Set Reconciliation".

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

What you are describing is called the common coin problem and has been introduced in [1]. One way to do this is to elect a leader and then let that leader flip a coin, for example, by using the lightest bin protocol[2]. Intuitively speaking, this works as follows: We have $n$ processes (=parties) and choose $m=n/\log n$ bins. In every round, every ...

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

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

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

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

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

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

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

Yes, such $(G,\le)$ pairs exist for any $\epsilon > 0$, any $r$, any $g$, and any even $d$. For details, see arXiv:1201.6675.

3

Decentralized algorithms for variants of this problem have been published in A distributed and privacy preserving algorithm for identifying information hubs in social networks and Social Influence Analysis in Large-scale Networks.

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