Questions tagged [dc.distributed-comp]

Theoretical questions in Distributed Computing

Filter by
Sorted by
Tagged with
-2
votes
1answer
786 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 ...
2
votes
0answers
101 views

Are the sets of executions of data-race free programs equal, when run on causal memory and on sequentially consistent memory respectively?

In the paper "Causal Memory: Definitions, Implementations, and Programming (Distributed Computing [DC] 1995)", the authors present a formal definition of causal memory, an abstraction of distributed ...
10
votes
2answers
574 views

Why is linearizability a safety property and why are safety properties closed sets?

In Chapter 13 "Atomic Objects" of the book "Distributed Algorithms" by Nancy Lynch, linearizability (also known as atomicity) is proved to be a safety property. That is to say, its corresponding trace ...
1
vote
0answers
48 views

What is the staleness in this execution of the $k$-atomic multi-writer register construction from $k$-atomic single-writer ones?

Background: $K$-atomicity is a consistency condition meaning that a read operation can return one of the values written by the last $k$ preceding writes in an order consistent with real time. It is a ...
10
votes
1answer
507 views

What is the advantage of designing deterministic distributed algorithms?

Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem. Paxos is deterministic in the sense that given the ...
1
vote
1answer
86 views

2PC with URBcast

Two phase commitment can be used for distributed transaction commitment. But it is consider as a blocking protocol when we used it with a best effort broadcast (BEBcast). My first question is, can we ...
4
votes
3answers
447 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 ...
1
vote
1answer
213 views

How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

I am trying to motivate, define, and implement $K$-atomic snapshot object. To this aim, I first give some basic definitions on atomic snapshot object and $K$-atomic object. Then, I will give my ...
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 ...
10
votes
3answers
579 views

Papers on fault handling in distributed systems

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

Is This Scheduling Problem NP-Hard?

The scheduling problem (arising from distributed computing) is defined as a decision problem as follows: Instance: A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-...
1
vote
1answer
158 views

Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm?

Backgroud I am reading Chapter 10 ``Fault-Tolerant Simulations of Read/Write Objects'' of the Book Distributed Computing (by Hagit Attiya & Jennifer Welch). Specifically, in section 10.2.3, it ...
3
votes
1answer
653 views

Termination of the Bellman-Ford algorithm in asynchronous distributed model

I'm looking for an algorithm to compute the BFS tree of a graph rooted in the leader processor $r$ in the asynchronous distributed model. The only requirement is $O(D)$ time complexity, where $D$ ...
-2
votes
2answers
311 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 ...
2
votes
1answer
109 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?
23
votes
1answer
690 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 ...
0
votes
0answers
256 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 ...
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 ...
13
votes
1answer
758 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 ...
1
vote
3answers
743 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 ...
7
votes
1answer
241 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
351 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 $\...
6
votes
1answer
220 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 ...
4
votes
1answer
130 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 ...
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 ...
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
212 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 ...
6
votes
1answer
151 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 ...
0
votes
1answer
670 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
240 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 ...
5
votes
1answer
121 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 ...
10
votes
1answer
346 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 $\...
13
votes
2answers
577 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 ...
11
votes
3answers
524 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
211 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, ...
6
votes
0answers
120 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, ...
13
votes
5answers
2k 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, ...
3
votes
5answers
777 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?
-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 ...
3
votes
1answer
430 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. ...
2
votes
0answers
755 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 ...
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 ...
7
votes
1answer
236 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: ...
10
votes
2answers
476 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
158 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?
10
votes
1answer
262 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 ...
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 ...
13
votes
2answers
261 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 ...