How to safely decrease a variable on a system without any concurrency control? [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Guide the asker to update the question so it focuses on a single, specific problem. Narrowing the question will help others answer the question concisely. You may edit the question if you feel you can improve it yourself. If edited, the question will be reviewed and might be reopened.

Closed 3 months ago.

The community reviewed whether to reopen this question 3 months ago and left it closed:

Original close reason(s) were not resolved

Improve this question

Simple question, let’s says I’ve an integer than must not go down below 0 and that I want to decrease it by 5 : then I can do something like this :

var-=5 ;
if var<0 abort() else send_payment();

In my case, an attacker has the possibility to launch 2 thread that will update var at the same time. This is a result of the design of the virtual platform/environment being used.
This means both threads would read the value of var at the same time and set it to the same decreased value. However, the payment would be indeed sent twice.

Normally programming languages and ᴏꜱ propose things such as mutex/futex or even transactional memory. But in the current case, the platform along the high level programming languages available provides no construct for serialization which means everything can be launched and updated in parrallel.

Beside authorizing a single person/entity to run the code, is there a way to create an algorithm that can prevent 2 part of the same code from being run at the same time ?

• Matt Timmermans: There are no "platforms" that support multiple interacting threads without some form of concurrency control.
• user2284570: @MattTimmermans then the TON virtual machine I’m working with is an exception. And the reason is performance : if developer were offered serialization, then the feature would be abused. What I want to do is to abort() all executions of a piece of code while it’s already being run by something else.
• trincot: Do you have access to the id of the current thread?
• user2284570: @trincot there’s no thread id. The system provides no way to know if the code is being run elsewhere. Of course besides global variables which are shared across threads (in reality there’s no thread but separate transactions). But there’s might be transaction id (but I don’t know how to use this since the id is unpredictable which makes it no different in my view from global variables).
• Matt Timmermans: If, by TON, you mean the "Telegram Open Network" crypto thing, then ... I didn't read all the docs, but for the stated use case, it wouldn't make any sense to allow any interaction between threads at all. I think you're imagining that var would be shared access, but it's not.

Answer 1

In general this calls for a mutex.

If the language does not provide mutexes out of the box, then maybe it has an atomic instruction that can read a state and modify it in the same atomic cycle (suffering no concurrency issues). Examples are test-and-set, fetch-and-add and compare-and-swap instructions. With any of these you can create a mutex.

If none of that is available either, then maybe you have an id that uniquely identifies the current thread. From comments I understand you have such an id that is called transaction id. With that you can create a (sort of) mutex variable (let's call it lock) that upon its creation is initialised as 0:

while (lock != transaction_id) { // While I don't have the lock
 if (lock == 0) { // If no-one is holding the lock
 lock = transaction_id; // Then take the lock
 short_pause(); // Allow concurrent threads to finish stealing the lock
 }
}
// Only one thread will see its lock-taking was successful
var -= 5;
lock = 0; // Release the lock as soon as possible.
if (var < 0) abort() else send_payment();

The short_pause must be long enough to ensure that any threads that still found the lock to be free (the if condition was true for them) will have finished executing the assignment to lock. This is the weak spot in the algorithm, as it may be possible there is a slow-executing concurrent thread that reads the lock as 0, but then only finishes its assignment to lock after the winning thread completes its assignment to lock, awaits the delay, checks lock again and finds that no-one updated it afterwards. This scenario would allow the slow thread to eventually exit the loop also, having updated lock. The longer the pause the less likely this is.

Peterson's Algorithm

If with the above algorithm you still have concurrent execution of the critical section, then maybe implement the more elaborate Peterson's algorithm (the one for more than two processes). You'll need to map transaction ids to array indices or use a dictionary data structure to implement it.