Questions tagged [dc.distributed-comp]
Theoretical questions in Distributed Computing
107
questions
1
vote
0
answers
32
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 ...
- 111
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 ...
- 354
1
vote
1
answer
40
views
Sequential idempotence
I want to coalesce multiple operations in a system into one and am currently studying under what conditions it is admissible. The conditions that are needed are stronger than idempotence and I'm ...
- 111
0
votes
1
answer
54
views
Selecting unique records from a large dataframe with many duplicate records
Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe?
Some sort of sampling algorithm?
1
vote
2
answers
203
views
Can concurrency models be compared in terms of some metrics?
In Seven Concurrency Models in Seven Weeks by Butcher, it compares Actor Model and Communicating Sequential Processes (CSP):
CSP is more flexible than actor model:
In actor model, the medium of ...
- 639
3
votes
1
answer
98
views
Lipschitz composable compressor
Def. We call $C: \mathbb R^d \to \mathbb R^d$ a $\delta$-compressor (or contractor) if for all $x$
$$\|C(x) - x\|^2 \le (1 - \delta) \|x\|^2$$
Intuitively, $C(x)$ is not too far from $x$. Note that $\...
- 201
-2
votes
1
answer
1k
views
Sequential vs Distributed algo question
If a certain graph problem in the $\textbf{sequential}$ setting is proven to have "no" better constant-factor approximation algorithm than say a 2-approx. algorithm in polynomial time, then does this ...
- 9
1
vote
0
answers
54
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 \...
- 2,329
1
vote
0
answers
107
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 ...
- 2,329
-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 ...
5
votes
1
answer
233
views
Confusion about a formal definition of PRAM consistency
I am reading the paper "Consistency in Non-Transactional Distributed Storage Systems" by Paolo Viotti and Marko Vukolić. The authors provide a comprehensive survey of various consistency semantics ...
- 2,329
4
votes
1
answer
122
views
"Learning" when test and train distributions don't match
We know that the theory of PAC-learning is distribution-free, i.e. assuming that the test and train distributions are the same, we have guarantees on learning the hypothesis.
Question: what if the ...
- 749
3
votes
1
answer
58
views
Complexity of distributively verifying that the diameter is small
Consider a graph $G=(V,E)$ and an integer parameter $k$.
I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
- 9,438
4
votes
0
answers
143
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 \...
- 9,438
1
vote
1
answer
80
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 ...
- 9,438
-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 ...
- 95
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 ...
- 131
1
vote
0
answers
102
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 ...
- 11
2
votes
1
answer
102
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 ...
- 121
1
vote
2
answers
263
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 <...
- 113
-3
votes
1
answer
68
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 (...
- 93
3
votes
1
answer
165
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,...
- 31
2
votes
1
answer
461
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 ...
- 21
5
votes
1
answer
707
views
Modern distributed computing book
Lynch's Distributed Algorithms book is a classic but it is from 1996 and rather out of date. Are there any recent distributed computing books that can be used as textbooks for a graduate distributed ...
- 4,001
0
votes
1
answer
76
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 ...
- 1
7
votes
1
answer
144
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 ...
- 2,329
0
votes
1
answer
165
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 ...
- 119
16
votes
0
answers
167
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 ...
- 211
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. ...
- 33
1
vote
1
answer
82
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 ...
- 21
2
votes
1
answer
82
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 ...
- 2,329
3
votes
1
answer
102
views
Results about computability power or limitations of shared read/write registers
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:
[1]. ...
- 2,329
3
votes
0
answers
222
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 ...
- 2,329
3
votes
1
answer
114
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 ...
- 2,329
10
votes
1
answer
636
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 ...
- 2,329
2
votes
1
answer
290
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?
- 141
0
votes
1
answer
57
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. ...
- 269
2
votes
1
answer
424
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 ...
- 123
-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 ...
- 121
13
votes
1
answer
1k
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 ...
- 2,329
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 ...
- 2,329
3
votes
1
answer
282
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 ...
- 2,329
7
votes
3
answers
227
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)$ ...
- 247
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 ...
- 31
4
votes
3
answers
542
views
What does it mean for CvRDT replicas to transmit their state "infinitely often"?
In Shapiro et al.'s SSS '11 paper on Conflict-Free Replicated Data Types for eventual consistency of distributed replicated objects, they describe a system model in which replicas transmit their state ...
- 323
2
votes
0
answers
604
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 ...
- 21
2
votes
0
answers
105
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,329
10
votes
2
answers
636
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 ...
- 2,329
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 ...
- 2,329
10
votes
1
answer
573
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 ...
- 201