Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Theoretical questions in Distributed Computing

-3
votes
0answers
56 views

Bridge between synchrony and asynchrony

As we know about synchrony and asynchrony. but there is some other synchrony exist between synchrony and asynchrony eg: Partial Synchrony Virtual Synchrony Eventual Synchrony How can I explain ...
-2
votes
0answers
21 views

how to install and use DistAlgo on eclipse with PyDev [migrated]

I install python, pydev and pip on eclipse, and I have a problem to add distalgo and executed the examples provided! can you give me an explanation? THANK YOU LINK TO DISTALGO: https://sites.google....
-1
votes
1answer
63 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
1answer
156 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 ...
4
votes
1answer
104 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 ...
3
votes
1answer
47 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 ...
4
votes
0answers
61 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 \...
1
vote
1answer
54 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 ...
0
votes
0answers
35 views

Confusion about “moves” in the valency argument for consensus numbers

In Section 5.1.1 "States and Valence" of the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit, it reads (emphasis added): A good place to start is to think about the ...
-3
votes
1answer
111 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 ...
3
votes
0answers
119 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 ...
1
vote
0answers
70 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 ...
2
votes
1answer
93 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 ...
1
vote
2answers
104 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 <...
-3
votes
1answer
41 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 (...
3
votes
1answer
145 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,...
2
votes
1answer
211 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 ...
4
votes
1answer
308 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 ...
0
votes
1answer
69 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 ...
7
votes
1answer
123 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 ...
0
votes
1answer
157 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 ...
15
votes
0answers
154 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 ...
2
votes
0answers
35 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. ...
1
vote
1answer
73 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 ...
2
votes
1answer
78 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 ...
3
votes
1answer
92 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]. ...
3
votes
0answers
96 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
1answer
98 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 ...
10
votes
1answer
449 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
votes
1answer
263 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?
0
votes
1answer
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. ...
1
vote
1answer
168 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 ...
-2
votes
1answer
190 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 ...
13
votes
1answer
823 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 ...
5
votes
0answers
129 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 ...
3
votes
1answer
217 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 ...
7
votes
3answers
213 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)$ ...
3
votes
0answers
175 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 ...
4
votes
3answers
330 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 ...
2
votes
0answers
303 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
0answers
90 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 ...
10
votes
2answers
444 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 ...
1
vote
0answers
39 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 ...
10
votes
1answer
414 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 ...
1
vote
1answer
76 views

2PC with URBcast

Two phase commitment can be used for distributed transaction commitment. But it is consider as a blocking protocol when we used it with a best effort broadcast (BEBcast). My first question is, can we ...
3
votes
0answers
227 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 ...
1
vote
1answer
137 views

Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm?

Backgroud I am reading Chapter 10 ``Fault-Tolerant Simulations of Read/Write Objects'' of the Book Distributed Computing (by Hagit Attiya & Jennifer Welch). Specifically, in section 10.2.3, it ...
4
votes
1answer
392 views

Is This Scheduling Problem NP-Hard?

The scheduling problem (arising from distributed computing) is defined as a decision problem as follows: Instance: A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-...
1
vote
1answer
199 views

How to Define and Implement (Single-Writer) K-Atomic Snapshot Object?

I am trying to motivate, define, and implement $K$-atomic snapshot object. To this aim, I first give some basic definitions on atomic snapshot object and $K$-atomic object. Then, I will give my ...
3
votes
1answer
589 views

Termination of the Bellman-Ford algorithm in asynchronous distributed model

I'm looking for an algorithm to compute the BFS tree of a graph rooted in the leader processor $r$ in the asynchronous distributed model. The only requirement is $O(D)$ time complexity, where $D$ ...