# Questions tagged [dc.distributed-comp]

Theoretical questions in Distributed Computing

101 questions
Filter by
Sorted by
Tagged with
62 views

### Unknown gaps in computation models

I'm looking for computatuon models where it is known that there are problems that we can solve in time T1 and T2. where T1 is smaller then T2 and it is unknown if there are problems where their ...
211 views

### The proof of P2b in Paxos made simple

I am reading Paxos Made Simple. I am quite confused about the proof of P2b. It said We would make the proof easier by using induction on n, so we can prove that proposal number n has value v under ...
41 views

56 views

### Does the following 2-rounds distributed algorithm approximates a maximal matching well?

Let $G$ be an undirected graph. I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible. Consider the following protocol for vertex $v$. Use a fair coin to ...
132 views

### Continous work distribution algorithm with failover

Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256. Is there an algorithm that ...
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 ...
120 views

### How does communication complexity relate to time complexity in distributed algorithms?

Some distributed algorithms (e.g. Bracha broadcast) runs in a constant number of rounds. I'm interested on how you'd analyse the time complexity of such algorithm, especially when the message size ...
242 views

### Paxos made simple, invariant P2c

I am reading Leslie Lamport's Paxos Made Simple paper. Can someone explain why $P2^c$ implies $P2^b$? $P2^b$ If a proposal with value $v$ is chosen, then every higher-numbered proposal issued ...
78 views

### How to design a scalable distributed consensus protocol that isn't vulnerable to long range attack

Research on distributed consensus has surged with the invention of Bitcoin and Blockchain. In these special cases we are looking for a distributed consensus algorithm that can scale to a number of ...
94 views

### Why do timeouts require synchronized clocks?

In Impossibility of distributed consensus with one faulty process @1985 by Fischer at al., the authors state (p375) We also assume that processes do not have access to synchronized clocks, so ...
126 views

### Confusions about the technique for verifying implementations of linearizable objects in [Herlihy and Wing, 1990]

In Section 4.3.2 entitled "Proof Method" of Herlihy and Wing, "Linearizability: A Correctness Condition for Concurrent Objects", 1990 the authors describe the technique for verifying ...
570 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 ...
118 views

### Distributed Consistency using Quorum approach

I'm stuck at distributed consistency when using a quorum. In this case we use N servers - 2/3N+1 for the read quorum (Nr), and <...
156 views

### Is it possible to boost the error probability of a Consensus protocol over dynamic network?

Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
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 ...
51 views

### Is it correct to call systems with agents without BDI multi-agent systems? [closed]

The question concerns two fields - multiagent systems in AI and in software engineering. As the source of the term comes from the AI field, I ask the question here. Traditionally multiagent system (...
148 views

### Does such model exists?

I have a problem on distributed graph, with the following model: 1. There is a Global Graph $G=(V,E)$ 2. There are $k$ computers. 3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph,...
71 views

### Number of rounds of iterative one-round distributed color reduction

We are talking about one-round coloring algorithms for distributed graphs. In "On the complexity of distributed graph coloring" (theorem 5.1) Kuhn and Wattenhoffer presented a one-round algorithm to ...
160 views

### What do these lower bounds really mean?

I was reading an abstract for a paper that gives a minimum number M of good agents that guarantees f-Byzantine gathering, if there are f Byzantine agents. It gives a lower bound of f+1 for strongly ...
74 views

### What does the contention-free communication assumption really mean in the context of DAG scheduling?

In many papers about DAG (directed-acyclic graph) scheduling in distributed systems, the authors make the assumption that the communication between the processors of the system where the DAG is ...
37 views

### centralized deterministic Spanner construction with low degree and low stretch

Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
79 views

### How to simulate sequential registers from causal ones?

Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For ...
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 ...
237 views

### Atomic snapshot algorithms on tree-structured shared registers

Background: Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety. The Gang of Six algorithm ...
93 views

I want to know more results about the computability power or limitations of shared $\texttt{read/write}$ registers/objects in distributed/concurrent computing theory. Two typical examples are: . ...
53 views

### Proof of causal multicast algorithm?

I'm reading Causal Memory: Denitions, Implementation and Programming and trying to get through the proof of liveliness of the algorithm around the middle of page 9, and I'm not really following it. ...
104 views

### Lower bounds and impossibility results for distributed transactions

I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations. To avoid ...
107 views

### In what sense, does a safe register exist?

In the paper "On Interprocess Communication", the author Leslie Lamport have developed a formalism for interprocess communication via shared registers based on lower-level, non-atomic operations and ...
469 views

### What are the major research issues in distributed transactions?

Background: Transaction processing has been a traditional research topic in database theory. Nowadays distributed transactions are popularized by the large-scale distributed storage systems which ...
272 views

### State of the art algorithms for community detection in graphs

Is anyone aware of the must read papers to get knowledge of the most recent algorithms and method for community detection in graphs, especially those that represent social networks?
191 views

### What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
890 views

### Correctness proofs of classic Paxos and Fast Paxos

I am reading the "Fast Paxos" paper by Leslie Lamport and get stuck with the correctness proofs of both classic Paxos and Fast Paxos. For consistency, the value $v$ picked by the coordinator in phase ...
132 views

### What is the significance of regarding the mutual exclusion problem as a problem of physics?

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote Most computer scientists regard synchronization problems, such ...
432 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 ...
227 views

### Concurrent data structures vs. Distributed data structures

In the context of multi-processor/multi-threaded systems, there are plenty of well-studied concurrent data structures, including stacks, queues, linked lists, etc. Here is an excellent survey on ...
217 views

### Job scheduling: minimizing number of reads

Consider the following scheduling problem: input: set of computations $C = \{c_1, ..., c_n\}$ set of computing nodes $P = \{p_1, ..., p_n\}$ Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ ...
182 views

### Election algorithm with unreliable messages and a certain timestamp

I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows: Messages are sent unreliably with an at-most-once sending Nodes are ...
320 views

### Totally ordered multicast with Lamport timestamps

I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the ...
729 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 ...
97 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 ...
### 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 ...