# Tag Info

### 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 ...
• 271
Accepted

You should first state the deadlock freedom property and the starvation freedom property more precisely. I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2. Freedom ...
• 9,551
Accepted

### Why are most mutex implementations unfair?

Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority ...
• 22.1k
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 ...
• 3,380

### 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 ...
• 71
Accepted

### What does "monotonicity" mean in the context of mutability

The author appears to be using the same (general) concept of "monotonicity" as in pure mathematics. Using the example of a vector, if the size of some particular ...
• 306

### Are Test and set primitives as powerful as semaphores?

Your hunch is correct, they aren't equivalent. Test-and-set has a consensus number of 2, which means, roughly speaking, that it is only able to efficiently synchronize between 2 processes. See Why is ...
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 ...
• 39k

### Contrasting Peterson’s and Dekker’s algorithms

In the following paper we give formal models for Peterson’s and Dekker’s algorithms (and some others) and we used model checker to prove their properties. Please, find our results in the table below (...
• 143

### generation-compare-and-swap, or GCAS, in CTries

Nice observation. To prevent the scenario that you are describing, the actual implementation in the Scala standard library uses a variant of the software RDCSS instruction when reading or modifying ...
• 140

### 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 ...
• 13.4k

### Two threads are waiting on a mutex. Which one is unblocked?

The short answer is "it depends". If there is truly nothing to distinguish thread B from thread C, then the answer on most scheduler implementations will likely be either "could be B or C, and you ...
• 22.1k

"No_of_Readers" is a shared variable hence, mutex is used to provide mutual exclusion to maintain data consistency. Consider the statement : No_of_Readers ++; In high level language it is only one ...
Accepted

Lets begin with defining some terms. Semaphore is one form of software implementation for process synchronization. It's an int value that is used by processes for the purpose of signalling. Only ...
• 311

### Why are most mutex implementations unfair?

'Priority inversion' is one reason that fairness can be undesirable. A low priority process hits the locked mutex and sleeps. Then a higher priority process hits it, and also sleeps. When the mutex ...

### Increment and Decrement on binary semaphores when their values are $1$ and $0$ respectively?

A binary semaphore has the wait() and the signal() method. The one which causes a process to stop is the wait() method, while the one that increments the counter x in the semaphore is signal(). If ...
• 591
Accepted

### Bounded waiting and starvation free in critical section problem

No, starvation-free doesn't imply bounded waiting. For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily ...
• 160k
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 ...
• 201

### Why are most mutex implementations unfair?

A fair mutex will spend more of its lifetime locked than an unfair mutex, all else being equal. Because a thread releasing an unfair mutex can always just unlock it. But a thread releasing a fair ...
Accepted

### Is Bounded Waiting satisfied for this 2 process Solution?

In the following, I treat the first two statements acquire(lock1) acquire(lock2) as "trying", the middle two statements ...
• 9,551

### Is bounded waiting satisfied in the 2 Process Solution?

A little remark first: The bounded waiting (BW) property is defined with respect to algorithms, which is in turn defined as a set of concrete executions. Thus, we cannot conclude whether an algorithm ...
• 9,551
Accepted

### “Standard” approach to syncing data?

I don't know that there is any "standard" or "best" approach, as the technique that is appropriate will depend on the setting. However, I recommend you start by looking at the algorithms used by ...
• 160k
Accepted

### How does coarser lock granularity cause an decrease in time required to acquire and release locks?

Fine-grained locks need to be acquired and released more often. Coarse-grained locks don't need to be acquired or released as often. Therefore, you're both right. For instance, suppose you're about ...
• 160k
Accepted

### Confusion in the solution to first readers-writers synchronization

But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer. It's a bit more subtle. The ...
Accepted

### Lamport logical clock: why event occurs in a process with smaller pid is treated earlier?

No, "it doesn't make sense". You are correct in the sense that that choice is not a logical consequence of any requirements and known truths. It could be considered as arbitrarily selected. Well, we ...
• 39k

### Synchronization in Distributed Systems

It is the other way around. We first model the system in a certain way, for instance we assume that there is a (or is no) global clock, or we assume that messages arrive or may fail, etc. Once we fix ...
• 20.7k
Accepted

### Exclusive queue problem

If you suspect that your solution is right, then try to prove it (since we are not dealing with foundations, e.g. how exactly is time represented in our system, the proof will be somewhat informal, ...
• 13.4k

### Understanding N process Peterson's algorithm

The way the N-process Peterson's algorithm works is slightly different than how the 2-process version is presented above. We can reason about the N-process version a little more like this: When a ...
• 2,092
Accepted

### Peterson's vs. Bakery Algorithm

a) what are the advantages/disadvantages over each other? According to the lecture note: Sections 17.4.1 and 17.4.3, we can summarize as follows: The original Peterson’s Algorithm works with only 2 ...
• 9,551