Vitalik publie un nouvel article « Memory access is O(N^[1/3]) » : exploration de la complexité d’accès à la mémoire et de l’efficacité des systèmes blockchain

Le 5 octobre, Vitalik a publié un nouvel article intitulé « Memory access is O(N^(1/3)) » pour explorer la complexité de l'accès à la mémoire. Il y discute des questions de complexité de « l'accès à la mémoire » dans les structures de données et les algorithmes, et avance que, dans certaines architectures ou modèles, le coût d'accès à la mémoire pourrait avoir une borne supérieure de O(N^(1/3)). Il souligne que la complexité temporelle classique des algorithmes de tri est de O(N log N), mais qu'il est nécessaire de réévaluer l'analyse de l'efficacité pour les ensembles de données de grande taille en tenant compte du goulot d'étranglement de l'accès à la mémoire. Ce sujet est particulièrement inspirant pour la conception des systèmes sous-jacents de la blockchain, notamment lors du traitement de grands états, de la synchronisation des nœuds, ainsi que des mécanismes de disponibilité des données (DA / échantillonnage de la disponibilité des données, etc.), où il est d'autant plus crucial de prendre en compte les limites d'efficacité de la « lecture et écriture en mémoire ».