Виталик опубликовал новую статью «Memory access is O(N^[1/3])»: исследование сложности доступа к памяти и эффективности блокчейн-систем.

5 октября Vitalik опубликовал новую статью «Memory access is O(N^(1/3))», в которой рассматривается сложность доступа к памяти. Он обсуждает проблему сложности «доступа к памяти» в структурах данных и алгоритмах, выдвигая предположение, что в некоторых архитектурах или моделях стоимость доступа к памяти может иметь верхнюю границу O(N^(1/3)). Vitalik отмечает, что классические алгоритмы сортировки имеют временную сложность O(N log N), однако при учёте узких мест доступа к памяти необходимо по-новому анализировать эффективность работы с большими наборами данных. Эта тема имеет важное значение для проектирования базовых систем блокчейна, особенно при обработке масштабных состояний, синхронизации узлов, а также механизмов доступности данных (DA / выборочная проверка доступности данных и др.), где необходимо особо внимательно учитывать узкие места эффективности операций чтения и записи в память.