Questions tagged [dc.distributed-comp]

Theoretical questions in Distributed Computing

Filter by
Sorted by
Tagged with
2
votes
1answer
107 views

bounds in centralized and distributed

If we know some lower bound of the solution of a problem in centralized setting, what can we say about the lower bound in a distributed setting?
9
votes
1answer
456 views

Is linearizability equivalent to consensus problem?

In the introduction of this paper Eventually Linearizable Shared Objects (PODC'10), the authors have presented the following statement without references: Linearizability, however, can be achieved ...
3
votes
1answer
171 views

Distributed file storage system - theoretical approaches

What are the main theoretical approaches to a distributed file storage system that allows files to be stored across a network of nodes, assuring their availability in case a node randomly loses ...
0
votes
0answers
231 views

Order of operations in 2 and 3 phase atomic commit protocols

I am currently reading through this http://research.microsoft.com/en-us/people/philbe/chapter7.pdf chapter about distributed recovery. The chapter focuses on 2 phase atomic commit (2PC) and 3 phase ...
13
votes
1answer
691 views

Is there a list of canonical problems in distributed systems?

Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about Solved Problems, Unsolved Problems and Non-Problems in Concurrency. The paper is easily readable, but ...
7
votes
1answer
234 views

Who said: “There is no central arbiter of truth in open distributed systems.”

Can anyone give me a reference to the origin of the statement "There is no central arbiter of truth in open distributed systems." Possibly it was Carl Hewitt in "The Challenge of Open Systems" Byte ...
3
votes
1answer
347 views

How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

The following question was first presented in MATHEMATICS of StackExchange. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such ...
5
votes
0answers
225 views

Distributed algorithms on sets

Given a connected arbitrary network $G = (V,E)$, where $V$ is a set of nodes (processors) and $E$ is the set of edges between the nodes. Each node $v _i$ is assigned a non-empty set $S(v _i)$, where $\...
19
votes
4answers
9k views

Why is the consensus problem so important in distributed computing?

In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One ...
1
vote
3answers
705 views

Does mathematical model for conccurent computations exist?

Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time? If yes, how are the concurrent computations ...
4
votes
1answer
119 views

Lower bound for orienting an asynchronous ring?

We require a lower message complexity bound of an asynchronous distributed algorithm that do the following: Given a undirected ring, with $n$ vertices, we want to let each node direct its edges to ...
-2
votes
2answers
287 views

Model checking Paxos

I have implemented consensus algorithm (based on Paxos). I have added some random test cases and it seems fine. To be sure, I want to do testing via model checking. I couldn't find a correct article ...
8
votes
0answers
256 views

Existence of “colouring matrices” — a generalisation

This is a generalisation of the following post: Existence of "colouring matrices". As the base case turned out to be fairly straightforward (in essence, precisely equal to the existence of Sperner ...
9
votes
2answers
193 views

Existence of “colouring matrices”

Edit: there is now a follow-up question related to this post. Definitions Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$. A $c \times c$ matrix $M = (m_{i,j})$ is said to be ...
7
votes
2answers
2k views

Efficient synchronization of two instances of an ordered list

What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move ...
6
votes
1answer
143 views

Minimal bandwidth required to synchronize two sets of values

We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the ...
4
votes
3answers
399 views

How to understand the “Availability” of the CAP theorem?

As we know, in the CAP theorem, "A" means "Availability". On wikipedia, the explanation of "Availability" is: Availability: a guarantee that every request receives a response about whether it was ...
0
votes
1answer
506 views

FloodSet in general networks

I would like to ask how could someone modify FloodSet algorithm to work in a general network, where process failures happen..Is it possible for it to work if a "crucial" [1] failure happens? [1]: As ...
5
votes
1answer
120 views

Honest Majority unconditional coinflipping without private channels

All communication is assumed to be by the parties taking turns making authenticated broadcasts. Is there a way for $n$ parties, each with access to ideal local randomness, to jointly choose a ...
23
votes
4answers
8k views

Major unsolved problems in distributed systems?

Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain. Something like membership protocols, data ...
5
votes
1answer
234 views

Average message complexity for the election problem on graphs

I am currently studying the election problem in distributed algorithms. There, I stumpled over one approach to implement a Chang-Roberts-like message extinction algorithm on graphs without requiring a ...
6
votes
1answer
200 views

O(N) leader election on torus with orientation and non-positional identity

I'm really confused by this. Apparently there is a deterministic algorithm that does leader election on a torus with orientation and non-positional identity using only O(N) messages. I'm unable to ...
14
votes
4answers
572 views

Infinitely large but locally finite computation problems

This question is inspired by a comment Jukka Suomela made on another question. What are examples of infinitely large but locally finite computation problems (and algorithms)? In other words, what ...
-2
votes
1answer
736 views

Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...
10
votes
1answer
328 views

Regular high-girth graph with a “locally uniform” total order on nodes

Definitions Let $\epsilon > 0$ and let $d$, $r$, and $g$ be positive integers (with $g > 2r+1$). Let $G = (V,E)$ be a simple, $d$-regular, undirected, finite graph with girth at least $g$. Let $\...
-3
votes
1answer
209 views

How can you tell between what is a “distributed” system versus “grid” computing versus “cluster” computing? [closed]

These terms seem to get thrown around rather vaguely, in my opinion, and was wondering if there were some hard-lined facts about what accounts for which category in these fields. If there aren't any, ...
11
votes
3answers
464 views

Efficient DAG comparison over a network

In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in ...
3
votes
1answer
425 views

What is “distributed computing” as a field of computer science?

I think it's field that studies distributed systems as described at http://en.wikipedia.org/wiki/Distributed_computing. There are distributed systems such as clusters and grids on top of this field. ...
13
votes
2answers
557 views

Decentralized algorithm for determining influential nodes in social networks

In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social ...
-2
votes
1answer
133 views

How to check if an algorithm in a distributed system worked within restraints?

I want to design a system in which a program is sent along with data and then it answers with the result. Is redundancy a must in this situation to check for correctness of the processed data? What is ...
2
votes
0answers
713 views

On the Bakery Mutual exclusion Algorithm

Lamport's Bakery Algorithm is one of the most elegant algorithms for mutual exclusion. The beauty of it is that it works even when the underlying system only provides a weak form of registers called ...
3
votes
5answers
715 views

How is Real-Time Computing defined?

How is real-time computing defined in theoretical computer science (e.g. complexity theory)? Are there complexity theoretic models designed to capture the real-time computation?
10
votes
5answers
1k views

Distributed Turing Machine?

I'm a master student focused on distributed systems but also interested on theoretical computer science. I was wondering if there is a formal representation of a distributed system on top of a turing ...
30
votes
10answers
1k views

Current parallel models for computation

The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s. Are these areas still active in terms of ...
23
votes
1answer
680 views

Estimating a percentile among distributed nodes without revealing values

I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it. Problem: Suppose a list of N numbers is shared among a set of participants ...
6
votes
0answers
119 views

Fair and “robust” fallback permutations

The following is a fun problem we stumbled into today. We have work we wish to distribute on machines $1..n$. Each piece of work is given a list of machines to try, in order. If any machine fails, ...
10
votes
2answers
427 views

Limits on lock-free collections?

David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way. This ...
1
vote
1answer
156 views

Is anyone actively researching distributed prediction models?

Is there any current, ongoing, research being performed, looking specifically at implementing prediction models on a distributed system? I'm specifically interested in work where the underlying system ...
1
vote
0answers
92 views

Is the Selflet system used for any active research?

Is the Selflet system (referenced in this paper - http://portal.acm.org/citation.cfm?id=1365562.1365597 for example) still seeing active research?
13
votes
5answers
1k views

Processor failures in distributed computing that are not crash or Byzantine

There are two main types of processor failures in distributed computing models: (1) Crash failures: a processor stops, and never starts again. (2) Byzantine failures: processors behave adversarially, ...
10
votes
1answer
241 views

What algorithms/reading matter would you recommend on resolving transactions / read-write locks?

A simplified classical database transaction can be viewed as: reading M items performing some calculation based on those reads writing some N results based on these calculations, which may include ...
13
votes
2answers
241 views

complexity of randomized gossiping

The gossiping problem in distributed systems is the following. We have a graph $G$ with $n$ vertices. Each vertex $v$ has a message $m_v$ that must be send to all nodes. Now, my question is in the ...
4
votes
1answer
194 views

Has ping based failure detector 'strong completeness' and 'weak accuracy'?

I was reading 'Unreliable Failure Detectors for Reliable Distributed Systems' (PDF) and I was wondering if ping (with increasing timeouts in case of failure) is in class S of failure detectors: ...
10
votes
3answers
556 views

Papers on fault handling in distributed systems

What papers on handling errors in distributed systems do you recommend?
3
votes
1answer
259 views

How is DHT different than regular hash tables in context to data/node lookup?

How is DHT different than regular hash tables in context to data/node lookup? This (introduction, 3rd paragraph) paper says: First, in addition to the insertion and deletion of items, DHTs must ...
5
votes
2answers
688 views

How is rebalancing of DHTs handled in case of failure or addition of new node?

I am reading about Dynamo-like DHT data storage applications like cassandra and project voldemort. I was curious, say: A new node is added to the cluster (since all the nodes are full) then the whole ...
7
votes
1answer
226 views

Is it possible to model maximization in a petri net without using inhibitor arcs?

Creating a petri-net that models the minimum function is quite simple: ...
6
votes
4answers
1k views

Distributed Elections using Logical Clocks (hints and tips)

I need to implement one of the logical clock algorithms (described here), to allow me to coordinate an election protocol for a distributed system. I'm struggling to work out how I might go about using ...
4
votes
3answers
347 views

How can I model this usage scenario mathematically?

I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system. The system behaves as follows: clients periodically issue multi-cast packets ...
41
votes
4answers
2k views

Why have we not been able to develop a unified complexity theory of distributed computing?

The field of distributed computing has fallen woefully short in developing a single mathematical theory to describe distributed algorithms. There are several 'models' and frameworks of distributed ...