SberTech ♥ Open Source, concurrency and reliable banking operations - problem analysis with Joker 2018
This weekend was Joker 2018 , it was interesting! But not only by speeches was the conference rich. All sponsoring companies tried to stand out against the “competitors” and we are no exception.
There was a lot of interesting things on the Sberbank-Technologies stand, but I want to tell you about how we stood out. Our Apache Ignite development team at SberTech prepared tasks and conducted a rally for those who dared to solve them.
Under the cut you are waiting for the task, the analysis of solutions and the ability to justify your own solution in the comments.

Petya and Kolya commit in Apache Ignite one feature per day.
Masha promptly tests each feature and rolls back commits containing errors.
Every third initial commit from Petit and the fifth from Kolya contain an error.
Petya spends an additional 2 days on correcting the error, Kolya 3, and they again
commit.
How many features will be committed for 86 working days, if Masha likes Petya,
and she notices his mistake only on the day when only he is mistaken?
Processing an unreliable bank during operations on a group of accounts blocks the keys of the
accounts in the order they are declared in the operation, i.e. from left to right.
Each deadlock is solved manually by the bank’s specialists and takes 10 times longer
than the usual operation.
Processing a reliable bank always blocks the keys in ascending order, but spends 2
times more time than a normal operation in an unreliable bank.
In both banks there are 10 accounts, the keys of the accounts are numbers from 1 to 10.
The processing of each bank requires 12 operations.
Operations are carried out in parallel, two at a time. Each operation affects up to 3
accounts:
- operation №1 (accounts: A, B, C), where A = i, B = A + 1, C = (A + B)% 10,
- operation №2 (accounts: D, E, F), where D = 11-i, E = D-1, F = (D + E)% 10,
i changes from 1 to 6.
The following pair of operations starts only after the full completion of the
previous one.
The keys are locked according to the policy of the bank, one in each of the operations, starting
with operation No. 1.
If the key is already locked in one of the operations, but is required to perform the other,
then the first operation is fully completed first, then the second one continues.
Forced execution of a pair of operations in sequential mode, as expected, occurs 2 times slower than in parallel.
What bank and how many times faster will complete operations?
Serezha is a very experienced programmer, extremely reckless and endlessly greedy.
Once he found the source code of his favorite tote on a githaba.
What is the minimum bet that Serezha can win?
A simplified tote listing is attached:
Best of all, the tasks were solved
- Evgeny Zubenko
- Alexander Novikov
- Andrei Golikov The
guys received branded backpacks, T-shirts and, of course, books.
There was a lot of interesting things on the Sberbank-Technologies stand, but I want to tell you about how we stood out. Our Apache Ignite development team at SberTech prepared tasks and conducted a rally for those who dared to solve them.
Under the cut you are waiting for the task, the analysis of solutions and the ability to justify your own solution in the comments.

Woe-committers
Petya and Kolya commit in Apache Ignite one feature per day.
Masha promptly tests each feature and rolls back commits containing errors.
Every third initial commit from Petit and the fifth from Kolya contain an error.
Petya spends an additional 2 days on correcting the error, Kolya 3, and they again
commit.
How many features will be committed for 86 working days, if Masha likes Petya,
and she notices his mistake only on the day when only he is mistaken?
Decision
Начиная с 13-го дня, образуется цикличность позволяющая Пете фиксить только каждую вторую свою ошибку.


Answer
64 + 54 = 118;
Villaribo and Villabaggio
Processing an unreliable bank during operations on a group of accounts blocks the keys of the
accounts in the order they are declared in the operation, i.e. from left to right.
Each deadlock is solved manually by the bank’s specialists and takes 10 times longer
than the usual operation.
Processing a reliable bank always blocks the keys in ascending order, but spends 2
times more time than a normal operation in an unreliable bank.
In both banks there are 10 accounts, the keys of the accounts are numbers from 1 to 10.
The processing of each bank requires 12 operations.
Operations are carried out in parallel, two at a time. Each operation affects up to 3
accounts:
- operation №1 (accounts: A, B, C), where A = i, B = A + 1, C = (A + B)% 10,
- operation №2 (accounts: D, E, F), where D = 11-i, E = D-1, F = (D + E)% 10,
i changes from 1 to 6.
The following pair of operations starts only after the full completion of the
previous one.
The keys are locked according to the policy of the bank, one in each of the operations, starting
with operation No. 1.
If the key is already locked in one of the operations, but is required to perform the other,
then the first operation is fully completed first, then the second one continues.
Forced execution of a pair of operations in sequential mode, as expected, occurs 2 times slower than in parallel.
What bank and how many times faster will complete operations?
hint
Итого:
— 6 итераций,
— 12 операций,
— во всех операциях, кроме одной, по 3 ключа.

— 6 итераций,
— 12 операций,
— во всех операциях, кроме одной, по 3 ключа.

Decision
Если все ключи разные — параллельное выполнение возможно.
Если нет — то нет, и возможен дедлок.

Если нет — то нет, и возможен дедлок.

Calculations
Ненадежный банк тратит на операцию 1 «такт», 2 в случае «сложностей» и целых 10 в случае дедлока.
Надежный банк тратит на операцию 2 «такта» и 4 в случае «сложностей». Дедлоков у надежного не бывает.

Надежный банк тратит на операцию 2 «такта» и 4 в случае «сложностей». Дедлоков у надежного не бывает.

Answer
Завершат одновременно.
Risks of public repositories
Serezha is a very experienced programmer, extremely reckless and endlessly greedy.
Once he found the source code of his favorite tote on a githaba.
What is the minimum bet that Serezha can win?
A simplified tote listing is attached:
classBid{ // Ставкаint amount;
boolean checked;
boolean restricted;
Bid(int amount) {this.amount = amount;}
}
~~~
AtomicReference<Bid> ref = new AtomicReference<>();
volatileboolean winner = false;
~~~
Thread validator = new Thread(() -> { // Запущен заранее!while (true) {
Bid bid = ref.get();
if (bid == null) continue;
if ((((bid.amount << 5) ^ 1_000_000) >>> 6) < (2 << 15))
bid.restricted = true;
bid.checked = true;
}
});
Thread payer = new Thread(() -> { // Запущен заранее!while (true) {
Bid bid = ref.get();
if (bid == null) continue;
if (bid.checked) {
if (!bid.restricted)
winner = true; // Выигрыш!
ref.set(null);
}
}
});
~~~
synchronizedbooleanmakeMeRich(int amount){ // Какую ставку сделает Сережа?if (winner) returnfalse; // Сережа должен торопиться - приз всего один
ref.set(new Bid(amount));
while(ref.get() != null) sleep(1);
return winner; // Если вернется "true" - Сережа едет на Бали
}
Tip # 1
— 131072?
— Нет, вылезай из ловушки :)
— Нет, вылезай из ловушки :)
Tip number 2
Какая минимальная ставка может принести Сереже выигрыш?
Tip number 3
Тут нет интуитивно ожидаемых гарантий видимости.
Добавить их можно следуюшим образом:
th1{
bid.restricted = true;
bid.checked = true;
}
...
th2{
while (!bid.checked) {
sleep(1);
}
assert bid.restricted; // 99.999%
}
Тут нет интуитивно ожидаемых гарантий видимости.
Добавить их можно следуюшим образом:
volatileboolean checked;
Tip # 4
Какая минимальная ставка может принести Сереже выигрыш?
Decision

Answer
Впрочем, «0» и даже «1» расценивались как верное решение.
java.lang.Integer#MIN_VALUE
Впрочем, «0» и даже «1» расценивались как верное решение.
Winners
Best of all, the tasks were solved
- Evgeny Zubenko
- Alexander Novikov
- Andrei Golikov The
guys received branded backpacks, T-shirts and, of course, books.