36 votes

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.
user avatar
  • 875
18 votes
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 ...
user avatar
  • 576
17 votes
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-...
user avatar
14 votes
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 ...
user avatar
14 votes
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 ...
user avatar
12 votes
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 ...
user avatar
12 votes

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 ...
user avatar
  • 276
10 votes
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 ...
user avatar
10 votes

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" ...
user avatar
  • 10.8k
8 votes

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 ...
user avatar
7 votes

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 ...
user avatar
7 votes

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 ...
user avatar
  • 140k
7 votes

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 ...
user avatar
  • 171
7 votes

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 ...
user avatar
7 votes
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 ...
user avatar
  • 18.8k
6 votes
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 ...
user avatar
  • 140k
6 votes

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 ...
user avatar
6 votes
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 ...
user avatar
  • 9,179
6 votes

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 ...
user avatar
  • 9,179
6 votes
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 ...
user avatar
6 votes
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 ...
user avatar
6 votes
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 ...
user avatar
  • 419
6 votes
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. ...
user avatar
  • 16.2k
6 votes
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 ...
user avatar
6 votes
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 ...
user avatar
6 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 ...
user avatar
  • 3,170
6 votes
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. ...
user avatar
5 votes

Additional clarification about Simultaneous Multithreading

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 ...
user avatar
5 votes

Difference between Parallel and Concurrent programming?

A slightly idealised answer, perhaps... Concurrency is a property of how a program is written. If a program is written using constructions like forks/joins, locks, transactions, atomic compare-and-...
user avatar
5 votes
Accepted

Good snapshottable data structure for an in-memory index

Use any kind of persistent/immutable (i.e., functional) tree-based data structure. The key is getting the locking right, as @Raphael pointed out in the comments. The nice thing about functional/...
user avatar

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