Theoretical questions in Distributed Computing
1
vote
1answer
42 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?
-1
votes
1answer
54 views
Consensus impossibility for arbitrary graph $G$
I know the proof of impossibility of achieving deterministic algorithm for consensus (the basic synchronous model) for 2 processes.
What is the proof for an arbitrary graph?
4
votes
0answers
62 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 ...
2
votes
1answer
122 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
117 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 ...
12
votes
1answer
210 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 ...
6
votes
1answer
157 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
187 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 ...
4
votes
0answers
168 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 ...
7
votes
2answers
353 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
291 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 ...
3
votes
1answer
83 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 ...
-1
votes
1answer
105 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 ...
7
votes
0answers
239 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 ...
8
votes
2answers
163 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 ...
3
votes
0answers
189 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 ...
5
votes
1answer
124 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
2answers
315 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 ...
0
votes
1answer
107 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
113 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 ...
5
votes
1answer
854 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
176 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
147 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 ...
12
votes
3answers
438 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, ...
-2
votes
1answer
427 views
Is there any proof that a network made of Turing machines can't solve the halting problem?
My question point to the fact that Turing machines are isolated by definition, but what if they can send, and receive information from/to to other Turing machines, what if they can be "interrupted" at ...
10
votes
1answer
300 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
170 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, ...
9
votes
3answers
338 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 ...
2
votes
1answer
295 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. ...
11
votes
2answers
415 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
130 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
244 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
438 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?
8
votes
5answers
575 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 ...
27
votes
10answers
843 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 ...
21
votes
1answer
584 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
101 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, ...
8
votes
2answers
352 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 ...
0
votes
1answer
125 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
89 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?
0
votes
0answers
83 views
Is an UUID-like navigation algorithm that would prevent agents from coming close to each other possible? [closed]
UUID is generated by a decentralized algorithm that uses current time and some value unique to each computer. Although computers don't ever talk to each other or to any central computer while ...
11
votes
5answers
727 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, ...
9
votes
1answer
187 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 ...
12
votes
2answers
209 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
172 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:
...
5
votes
3answers
351 views
Papers on fault handling in distributed systems
What papers on handling errors in distributed systems do you recommend?
3
votes
1answer
182 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
195 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 ...
7
votes
1answer
189 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:
...
4
votes
4answers
453 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 ...
