Twin paradox and distributed systems

In the future we definetely will travel through the Universe. And the speed of the starships will be close to the speed of light, or even probably beyond it (as you can see in some movies). Therefore according to the twin paradox all the clocks will have different time. Intergalactic distributed computer network will be really difficult, and eventually (I hope so) constistent.

So, I have some questions:

How will the clocks in computers on the starships, stations, and planets be syncronized?

There are special data structure called CRDT (conflict-free replicated data type) but is also uses timestamps.

Probably we need to find some source/invariant of global time (but how can we break the laws of physics (may be quantum physics can help here)), or find a way to make amendments base on straship acceleration/speed/traveled distance if it is possible.

iCTF 2018

Today the historical event happened. The team SiBears I'm playing with won first place in iCTF 2018 CTF contest.

First time I've played iCTF in 2011. And it was hard but really interesting. And I'm very proud that out team has finally won, and finished at first place, because this is one of the first (if not the first) classic CTF competitions. Thanks to the UCSB iCTF team for such great event.

Surely You're Joking, Mr. Feynman!

Recently I've finished reading the book "Surely You're Joking, Mr. Feynman!". This book was recommended in the book "A Mind For Numbers: How to Excel at Math and Science (Even If You Flunked Algebra)".
I really enjoyed reading it. The great and funny stories from the life of the great man.

Recommend this book to everyone, it is really good.

Гипотеза RUM

Группа разработчиков из DASlab (Лаборатория систем обработки данных) Гарвардской школы инженерных и прикладных наук Джона А. Полсона (SEAS) разработали гипотезу RUM (Read, Update, Memory, то есть Чтение, Обновление/Запись и Память).

Гипотеза RUM описывает повсеместный компромисс между оптимальным чтением, записью и используемой памятью у методов доступа к современным системам данных.

При построении методов доступа к современным системам, каждый сталкивается с одними и теми же фундаментальными задачами и проектными решениями.
Есть три величины, которые исследователи всегда стараются свести к минимуму:

• накладные расходы на чтение (R)
• накладные расходы на обновление/запись (U)
• накладные расходы на память (оперативная память, диск, и др.) (M)

три этих параметра (накладные расходы RUM) образуют треугольник:

Накладные расходы RUM - на чтение, запись и используемую память.

Гипотеза RUM:
разработка методов доступа, которые устанавливают верхнюю границу для двух (из трёх) накладныех расходов (оверхедов) RUM, приводит к жёсткой нижней границе для третьего (оверхеда), которая не может быть дополнительно уменьшена.

TLDR: Чтение, Обновление/Запись, Память — оптимизация двух за счет третьего.

Накладные расходы на чтение выражаются в усилении чтения (read amplification), то есть отношении объёма фактически прочитанных данных к объему необходимых данных.
Аналогично накладные расходы на обновление/запись выражаются в усилении записи (write amplification), а накладные расходы на память в усилении занимаемой памяти (space amplification).
Здесь усилении записи (write amplification) — это отношение объёма фактически записанных данных к реально изменённому, а усиление занимаемой памяти (space amplification) — отношение объёма данных + объём вспомогательных данных таких как индексы и другие метаданные, к объёму самих данных.

При разработке методов доступа к системам, существует множество подходов, каждый из которых предназначен для конкретного случая использования. Например, чтобы минимизировать стоимость чтения данных, можно использовать индексы на основе хэш-таблиц или структуры данных с логарифмической сложностью, такие как Hash table, B-Tree, Skiplist, Trie и др.

Структуры с оптимизацией записи — уменьшают накладные расходы на запись, сохраняя обновления во вторичных структурах данных. Основная идея заключается в объединении обновлений с последующим применением к системе управления данными. Примеры: LSM-tree, Partitioned B-tree (PBT), алгоритм Materialized Sort-Merge (MaSM), алгоритм Stepped Merge и Positional  Differential Tree (PDT), и др.

Способы эффективного использования памяти предназначены для уменьшения накладных расходов на хранение данных. К ним относятся методы сжатия и индексы с потерями, такие как Фильтр Блума, HyperLogLog, Count-min sketch, Bitmap, Zonemap, Sparse индексы, и др.

Ссылки:
[1] The RUM Conjecture - DASlab @ Harvard University
[2] Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, et al.: “Designing Access Methods: The RUM Conjecture,” at 19th International Conference on Extending Database Technology (EDBT), March 2016. doi:10.5441/002/edbt.2016.42