Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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.
DylanSp's user avatar
  • 865
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-...
Derek Elkins left SE's user avatar
13 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 ...
Shadow Template's 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 ...
oerkelens's user avatar
  • 276
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 ...
ghellquist's user avatar
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 ...
Joel's 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 ...
Wandering Logic's user avatar
7 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 ...
Yuval Filmus'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 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 ...
Pseudonym's user avatar
  • 22.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 ...
ComicSansMS's user avatar
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. ...
Derek Elkins left SE's 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-...
John Wickerson's user avatar
5 votes
Accepted

How does lack of deadlock relate to computability in process calculi?

I think you are asking about expressivity of concurrent programming languages. This is a deep and not well-understood field. For example you say that "the $\pi$-calculus [...] has the power to ...
Martin Berger's user avatar
5 votes

Write Serialization for Cache Coherence in the presence of Store Buffers

Situations like the one you describe are the reason why processor manuals for architectures with store buffers such as intel tend to state that two stores by cores i and j are seen in the same order ...
Kai's user avatar
  • 908
5 votes
Accepted

What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?

A semaphore is a counter, that counts the number of processes that have access to a resource. If a resource can service n processes, n is decremented each time a process accesses the resource, and ...
EL Dendo's user avatar
  • 249
5 votes

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 ...
Gilles 'SO- stop being evil''s user avatar
5 votes

Whats exact definition of 'atomicity' in programming?

If an operation X is atomic, that means that anyone observing the operation will see it either as not yet started, or as completed, and not in any state that is partially completed. That's it. ...
gnasher729's user avatar
  • 30.4k
5 votes

Cache coherence is worthless and does nothing?

It is false to assume that a write to a cache-line will cause a flush to main memory. Caches on modern CPUs are always coherent. Modern caches are also write behind caches meaning that in theory they ...
pveentjer's user avatar
  • 319
4 votes

Who needs linearizability?

First, linearizability and serializability are not directly comparable. As the table below shows, the main difference is that on the left hand side, all individual operations are atomic (like having a ...
Sriram Srinivasan's user avatar
4 votes

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 (...
meolic's user avatar
  • 143
4 votes

Why must uncommitted transactions be undone in backwards order?

This is right because transactions are built on top of each other and the outcome of a transaction is very much dependent on the situation before it was committed. Let's look at financial ...
thebeancounter's user avatar
4 votes

How probable is a deadlock in the dining philosophers problem

the dining philosopher problem seems to be somewhat of a pedagogical "toy" example of concurrency and (dead)locking concepts for educational purposes. however it is studied seriously in some ...
vzn's user avatar
  • 11k
4 votes
Accepted

Software mutexes and consensus number 1

Herlihy's result, indeed the whole paper, is about wait-free synchronization. Corollary 1 states that there is no wait-free two-process consensus protocols using atomic registers. Wait-free is defined ...
Gilles 'SO- stop being evil''s user avatar
4 votes
Accepted

Reader and Writer mutex

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 ...
Ugnes's user avatar
  • 311
4 votes

Reader and Writer mutex

"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 ...
Akash Mahapatra's user avatar
4 votes

Does mutual exclusion hold in this case?

A mutual exclusion solution should satisfy not only the mutual exclusion property but also the deadlock property. Deadlock occurs when one or more processes are "trying to enter" their critical ...
hengxin's user avatar
  • 9,561
4 votes
Accepted

Why deadlock in cigarette smokers problem

Agent A consumes agentSem, and produces tobacco and paper. That might make Smoker I smoke but he is late: Smoker II already took the paper and Smoker III took tobacco. Now, all the smokers are stuck,...
chi's user avatar
  • 14.6k
4 votes

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 ...
Jim Sawyer's user avatar
4 votes
Accepted

How can a spinlock progress when it's busy-waiting?

There might be other CPUs in the system, if one is busy waiting, another can be doing something. Furthermore, if the OS uses preemptive scheduling, the thread doing the busy wait might be preempted ...
Amaury Pouly's user avatar
  • 1,181

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