14 votes

Difference between Lamport timestamps and Vector clocks

Summary: Lamport timestamps and vector clocks are both logical clocks, and both provide a total ordering of events consistent with causality. Vector clocks allow you to determine if any two ...
BMiner's user avatar
  • 271
13 votes

External consistency vs linearizability

External consistency doesn't have a fixed meaning. In this context, it has the meaning appearing in the very next sentence in the document: For any two transactions, $T_1$ and $T_2$ (even if on ...
Yuval Filmus's user avatar
9 votes

How do Functional Reactive Programming and the Actor model relate to each other?

I wanna point out how they are different from a practical point of view: 1) actors send messages to other actors, this message passing is described explicitly and imperatively. For example: ...
jhegedus's user avatar
  • 255
9 votes
Accepted

Confused between 2 phase locking and 2 phase commit

These are two different things that have two different goals. The two-phase locking protocol is designed to guarantee serializability for transactions that access concurrently a single, centralized ...
Renzo's user avatar
  • 809
7 votes
Accepted

What is the consensus algorithm that requires an odd number of nodes?

To my knowledge there is no quorum-based consensus algorithm that requires an odd number of nodes (processes). That's because such algorithms don't require a majority in the sense that a higher number ...
gdvieira's user avatar
7 votes

Distributed vs parallel computing

Here is a recent paper that is worth reading: Michel Raynal: "Parallel Computing vs. Distributed Computing: A Great Confusion?", Proc. Euro-Par 2015, doi:10.1007/978-3-319-27308-2_4 Abstract: ...
Jukka Suomela's user avatar
7 votes
Accepted

Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

The paper says By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$ Here is a proof: The set of configurations forms the nodes ...
jbapple's user avatar
  • 3,380
7 votes
Accepted

Why is Two-Phase Commit (2PC) blocking?

Is it because the cohorts don't employ timeout concept in 2PC? Yes, in one case they can not use a timeout. It is described in the paper too (II.B.1): The Two-Phase Commit Protocol goes to a ...
tevemadar's user avatar
  • 281
7 votes

Why are forks in the Blockchain eventually resolved?

If we simplify and assume that each miner randomly guesses a hash (as opposed to being more systematic) and we discretize time, say into minutes, then each minute each miner is hoping to "roll" the ...
Derek Elkins left SE's user avatar
7 votes

Difference between Lamport timestamps and Vector clocks

Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ...
Carmine's user avatar
  • 71
7 votes
Accepted

What is the difference between Consensus and Leader Election problems?

This is not a matter of terminology: they're related, but different concepts. A consensus algorithm is one that allows all the participants in a distributed system to choose a value from a set in ...
Gilles 'SO- stop being evil''s user avatar
6 votes

Why is the commit phase in PBFT necessary?

PBFT is a master piece, for its technical breakthrough and exquisitely precise language. Many descriptions on the protocol details worth reading multiple times to grasp all the nuances. I will: quote ...
Alex Xiong's user avatar
6 votes
Accepted

Are vector clocks useful in centralized systems?

No, there's no need for a vector clock in a centralized system. A vector clock uses a $N$-vector of timestamps, where $N$ is the number of computers in the distributed system and the $i$th component ...
D.W.'s user avatar
  • 159k
6 votes
Accepted

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

In parallel computing, the threads can talk to each other and exchange information during the computation. In nondeterminism, the only "communication" between threads is that we compute the OR of all ...
sdcvvc's user avatar
  • 3,491
6 votes
Accepted

Algorithm notation

⋃ is the n-ary union operator, similar to how ∑ is the n-ary addition operator. So, in the same way that ∑j someExpressionDependingOnJ means "add the values of all the different instances of ...
Jörg W Mittag's user avatar
5 votes
Accepted

How to resize a large, distributed hash table?

Yes, after storing many items in a distributed hash table spread over a hundred computers, if hypothetically we used the sort of hash function popular for in-RAM hash table, adding another computer ...
David Cary's user avatar
5 votes

How do you compute the time complexity of distributed algorithms?

Time complexity is always measured relative to some model. For example, the $\Theta(n \log n)$ bound on sorting is the number of comparisons performed. If comparisons are not constant time, then the ...
Joey Eremondi's user avatar
5 votes
Accepted

Lamport logical clock: what does partial mean in the concept of `Partial ordering`?

The "partial ordering" in the papar means partial order as in standard mathemtics theory. To be more rigorous, the "partial ordering" in that paper, also called "irreflexive parital ordering" in that ...
John L.'s user avatar
  • 39k
4 votes

Vector clocks: Why is it necessary to increment my clock on receiving a message?

Look at the definition of $<_H$. We say that $e_1<_H e_2$ (event 1 happened before event 2) if: $e_1,e_2$ took place in the same process, and $e_1$ happened first (events within the same ...
Ariel's user avatar
  • 13.4k
4 votes

blockchain database - why so redundant

See https://en.wikipedia.org/wiki/Blockchain_(database)#Decentralization, which states that "Every node in a decentralized system has a copy of the blockchain. This avoids the need to have a ...
Robert Harvey's user avatar
4 votes

What is the consensus algorithm that requires an odd number of nodes?

"Always have an odd number of replica set members" is a common simplification of the MongoDB replica set election process and best practices for deployment, but certainly not a strict requirement. ...
Stennie's user avatar
  • 141
4 votes
Accepted

Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?

All of these are, generally speaking, called "synchronous models", they are pretty similar to each other, and especially in the context of fault-tolerant algorithms they are very different from "...
Jukka Suomela's user avatar
4 votes

Where does the FLP impossibility proof depend on allowing a single process failure?

The part of the original paper's proof that requires node failure to prove the impossibility is case 2 of lemma 3. This case assumes that there is a "finite deciding run from C0 in which p takes no ...
trungaczne's user avatar
4 votes
Accepted

Can I prove that I have x such that f(x) < c without revealing x?

If the function $f$ is publicly known and is efficiently computable, it is possible for Bob to prove that he knows a value $x$ such that $f(x)<c$. This is known as a zero-knowledge proof of ...
D.W.'s user avatar
  • 159k
4 votes
Accepted

How do you compute the time complexity of distributed algorithms?

You understood it right. The standard models of distributed computing typically assume that local computation is free. It follows that in the LOCAL model of distributed computing, you can solve any ...
Jukka Suomela's user avatar
4 votes
Accepted

Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?

You're right that this is an impossible problem to solve in an asynchronous distributed system, and you're also right that it would solve a lot of problems if we could get a totally ordered clock. But ...
jordojuice's user avatar
4 votes
Accepted

Invariant vs Assertion vs lemma

All terms describe formal claims that are true. The main difference is in how they are used. A lemma is mathematical claim that is (generally) true. In textbooks, Lemma's are usually either proven, ...
Discrete lizard's user avatar
  • 8,248
3 votes
Accepted

Overflow of integer counter in distributed systems

In general: Paxos algorithm uses unbounded integers to tag data. In practice, however, every integer handled by the processors is bounded by some constant $2^b$ where $b$ is the integer memory ...
Ivan's user avatar
  • 161
3 votes
Accepted

Can we say that Zookeeper updates are ACD (ACID without the I)?

Atomicity is not about being able to implement "atomic locks" or not. Consistency as used in the CAP theorem (i.e. the C in CAP) is not the same thing as Consistency in ACID, and Consistency in CAP ...
Derek Elkins left SE's user avatar
3 votes

Both shared-memory and distributed-memory

A couple of points, but in general the diagram doesn't provide enough information to make any real conclusions. First, this isn't the typical layout for shared memory architecture. Typically shared ...
theoneandonly2's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible