# Tag Info

### Why must uncommitted transactions be undone in backwards order?

Original transactions: Insert record $r$. Update some field $f$ of $r$. Forward undo: Delete record $r$. Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.
• 875
Accepted

### Why is the consensus number for test-and-set, 2?

Just to make sure we are on the same page, first let us consider these three definitions: Definition. Test-and-set is a read-modify-write instruction on some binary register (let's just say that 0 ...
• 576
Accepted

### Is it possible for a stack-based programming language to be concurrent?

So, can stack-based programming languages be concurrent? Sure. Could they achieve concurrency by using multiple stacks at the same time or something alike? Already for normal languages multi-...
• 11.8k
Accepted

### Why is a program with only atomics in SC-DRF but not in HRF-direct?

Hopefully they didn't say explicitly say exactly "a program consisting only of atomics is race free in SC-DRF." That's incorrect. They do say that "[in] scoped synchronization ... it is possible to ...
• 17.3k
Accepted

### Are there hardware lock implementations without test-and-set or swap?

Yes, you can implement mutual exclusion with only memory load and store instructions. There is a long tradition of devising successively simpler solutions to this problem. The earliest version that ...
• 17.3k
Accepted

### Why is quiescent consistency compositional, but sequential consistency is not

Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you. First, let's start with sequential ...

### Why must uncommitted transactions be undone in backwards order?

To add to DylanSp's answer, trying to update a field in a non-existing record will fail, but the result will still be the expected result: record r does not exist. However, consider a situation where ...
• 276
Accepted

### Bakery algorithm: what is the choosing[] boolean array for?

choosing[i] is true while number[i] is being updated to be larger than all the other values in the ...

### Why would you use a monitor instead of a semaphore?

They are nearly interchangeable and one can be built out of the other. It is somewhat language dependent which is implemented/ preferred (eg Java has built-in monitors using "synchronize" ...
• 10.8k

### Is it possible for a stack-based programming language to be concurrent?

I know a bit about FORTH so I will confine myself to that. It is a low level language, giving you as programmer access to all the hardware resources. So you can do whatever you like. Concurrency In ...
• 396

### Why is the consensus number for test-and-set, 2?

The wikipedia article does have a reference that answers you question, but perhaps you don't want to read that 26 page paper. I'll give a simplified version of the (quite technical) proof, showing ...

### Why are multi-threading programs more prone to errors?

Overview Multi-threaded programs are more prone to errors than single-threaded programs because of the problem of concurrency bugs. Concurrency is hard for most developers to reason about, which ...
• 140k

### Why must uncommitted transactions be undone in backwards order?

Let's go by analogy: say you're going out for dinner. Put socks on. Put shoes on. Stand up. Walk to door. Then you get a phone call. Dinner plans cancelled. Take socks off. Take shoes off. Sit ...
• 171

### Write Serialization for Cache Coherence in the presence of Store Buffers

From a coherence perspective, I think your example is coherent. All processors believe that the write and read from A happened first, then the write and read from B happened later. From a ...
• 17.3k
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 ...
• 18.8k
Accepted

### What is the fastest way to a Publish/Subscribe pattern?

Since you are asking on CS.SE rather than StackOverflow, I presume you are looking for a principled look at the fundamental underlying problem and principled solutions to the general problem, from a ...
• 140k

### What is the practical relevance of textbook mutual exclusion algorithms?

Answer: none. That's not what those sections of Herlihy and Shavit's The Art of Multiprocessor Programming are about. In the chapters on mutual exclusion Herlihy and Shavit are not giving you ...
• 17.3k
Accepted

### Linearizability and Serializability in context of Software Transactional Memory

About your definitions: The basic idea of Serializability ($\textsf{SR}$) is correct. However, it does not have to constrain itself on the your assumption that ...
• 9,179

### Implementing wait-free consensus with queues

This paper Some results on the impossibility, universality, and decidability of consensus (by Prasad Jayanti and Sam Toueg, 1992) directly answers your question. We study how initialization of shared ...
• 9,179
Accepted

### Why would you use a monitor instead of a semaphore?

We finally discussed why you would use a monitor instead of a semaphore in the lecture today. It basically comes down to this: The monitor and the semaphore are equally expressive, meaning you can ...
• 296
Accepted

### Why there must be a relationship between user threads and kernel threads?

This section of the book appears to be talking about how the details of the threading and scheduling are implemented for a user mode program. When threading first became popular, most operating ...
Accepted

### User level threads are transparent to the kernel?

As, the linked answers and the explanations provided by your textbooks describe that, user level threads are transparent to the kernel, yes they are indeed. Kernel Level threads are not transparent ...
• 419
Accepted

### example for weakly fair v.s. strongly fair scheduling in concurrency

If you are familiar with temporal logic, the difference is quite easy to demonstrate: Weak fairness is $FGp\to Fq$. That is, if $p$ holds from some point and on, then $q$ will hold eventually. ...
• 16.2k
Accepted

### Lamport’s fast mutual exclusion algorithm intuition

In what sense are this locks fast/slow? Lamport optimizes for a very specific scenario, as pointed out in the paper: The current belief among operating system designers is that contention for a ...
• 294
Accepted

### Does mutual exclusion hold in this case?

Your friend is correct. In your context, mutual exclusion holds if at most one process is at a critical section at any given time. You state that you feel that this interpretation is wrong, but you ...
• 269k
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,170
Accepted

### What does synchronous and asynchronous mean in computer science?

As Discrete lizard suggests, there is not some precise CS-wide definition for these terms. Generally, you should not expect terms and notation to always mean the same thing even within a single field. ...
• 11.8k

The confusion seems to be different terminology used in different sub-communities of computer science. To most computer scientists, simultaneous multithreading, is thought of as any situation in ...
• 17.3k