Questions tagged [dc.distributed-comp]

Theoretical questions in Distributed Computing

26 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
0 answers
168 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 ...
Irvan's user avatar
  • 211
8 votes
0 answers
261 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 ...
Jukka Suomela's user avatar
6 votes
0 answers
124 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, ...
sclv's user avatar
  • 1,379
5 votes
0 answers
140 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 ...
hengxin's user avatar
  • 2,329
5 votes
0 answers
229 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 $\...
AJed's user avatar
  • 644
4 votes
0 answers
145 views

2-hop distributed coloring in the CONGEST model

Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$. A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
R B's user avatar
  • 9,448
3 votes
0 answers
142 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 ...
lamba's user avatar
  • 131
3 votes
0 answers
227 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 ...
hengxin's user avatar
  • 2,329
3 votes
0 answers
200 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 ...
dirkk's user avatar
  • 31
3 votes
0 answers
267 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 ...
hengxin's user avatar
  • 2,329
2 votes
0 answers
45 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. ...
SSS's user avatar
  • 33
2 votes
0 answers
616 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 ...
Fabrizio's user avatar
2 votes
0 answers
106 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 ...
hengxin's user avatar
  • 2,329
2 votes
0 answers
784 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 ...
kryptos's user avatar
  • 460
1 vote
0 answers
33 views

Application LCL definition to vertex coloration

I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2) An Locally ...
Qise's user avatar
  • 111
1 vote
0 answers
57 views

How to justify this causally consistent execution in the $(vis, ar)$ framework for distributed consistency models?

In Figure 5.1 of the book "Principles of Eventual Consistency" by Sebastin Burckhardt, 2014, Causal Consistency (CC); wiki is (mainly) defined as the conjunction of $hb \subseteq vis$ and $hb \...
hengxin's user avatar
  • 2,329
1 vote
0 answers
111 views

Confusion about the visibility and arbitration relations in a formal framework for distributed consistency models

In the POPL'14 paper "Replicated Data Types: Specification, Verification, Optimality" and the book "Principles of Eventual Consistency", the authors propose a formal framework for ...
hengxin's user avatar
  • 2,329
1 vote
0 answers
103 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 ...
very's user avatar
  • 11
1 vote
0 answers
56 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 ...
hengxin's user avatar
  • 2,329
1 vote
0 answers
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?
blueberryfields's user avatar
0 votes
0 answers
20 views

The minimal number of messages required to solve the mutual exclusion problem in a symmetric distributed system

In the seminal paper introducing their namesake algorithm for solving the mutual exclusion problem in a distributed system, Ricart and Agrawala assert (in the first paragraph of section 4 Message ...
Evan Aad's user avatar
  • 354
0 votes
0 answers
271 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 ...
user avatar
-1 votes
1 answer
80 views

How to know if a problem is distributable?

I am new to the world of Parallel computing and that is why don't know exactly where I should look at or search to get the answer. Is there any theorem or just general theory determining which code ...
Turkhan Badalov's user avatar
-2 votes
1 answer
204 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 ...
gmr's user avatar
  • 121
-2 votes
1 answer
134 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 ...
alfa64's user avatar
  • 97
-3 votes
1 answer
159 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 ...
alamar's user avatar
  • 95