Questions tagged [dc.distributed-comp]
Theoretical questions in Distributed Computing
26
questions with no upvoted or accepted answers
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 ...
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 ...
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, ...
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 ...
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 $\...
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 \...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
-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 ...
-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 ...
-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 ...
-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 ...