Vitalik publica un nuevo artículo "Memory access is O(N^[1/3])": analiza la complejidad del acceso a la memoria y la eficiencia de los sistemas blockchain

El 5 de octubre, Vitalik publicó un nuevo artículo titulado “Memory access is O(N^(1/3))”, en el que explora la complejidad del acceso a la memoria y discute el problema de la complejidad del “acceso a memoria” en estructuras de datos y algoritmos. Propone que, bajo ciertas arquitecturas o modelos, el costo de acceder a la memoria podría tener un límite superior de O(N^(1/3)). Señala que la complejidad temporal de los algoritmos clásicos de ordenamiento es O(N log N), pero que, al considerar los cuellos de botella en el acceso a la memoria, es necesario reevaluar el análisis de eficiencia para conjuntos de datos a gran escala. Este tema resulta inspirador para el diseño de sistemas subyacentes de blockchain, especialmente al tratar con estados a gran escala, sincronización de nodos y mecanismos de disponibilidad de datos (DA / muestreo de disponibilidad de datos, etc.), donde es aún más importante considerar cuidadosamente los cuellos de botella en la eficiencia de “lectura y escritura de memoria”.