# Questions tagged [dc.distributed-comp]

Theoretical questions in Distributed Computing

104 questions
Filter by
Sorted by
Tagged with
434 views

10k 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 ...
740 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 ...
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 ...
308 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 ...
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 ...
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 ...
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 ...
150 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 ...
445 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 ...
640 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 ...
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 ...
9k 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 ...
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 ...
219 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 ...
608 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 ...
777 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 ...
346 views

199 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: ...
579 views

### Papers on fault handling in distributed systems

What papers on handling errors in distributed systems do you recommend?
261 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 ...