Vitalik released a new article "Memory access is O (N ^ [1/3]) ": exploring memory access complexity and blockchain system efficiency

On October 5th, Vitalik released a new article "Memory access is O (N ^ (1/3)) " to explore memory access complexity, discuss the "memory access" complexity problem in data structures and algorithms, and propose that under some architectures or models, the cost of accessing memory may have an upper bound of O (N ^ (1/3)). He pointed out that the time complexity of the classical sorting algorithm is O (N log N), and when considering the memory access bottleneck, the efficiency analysis of large-scale datasets needs to be re-examined.
This topic is instructive for the design of the underlying system of the blockchain, especially when dealing with large-scale state, node synchronization, and data availability (DA/data availability sampling, etc.) mechanisms, the efficiency bottleneck of "read and write memory" needs to be carefully considered.