Vitalik publica novo artigo "Memory access is O(N^[1/3])": explorando a complexidade do acesso à memória e a eficiência dos sistemas blockchain

Em 5 de outubro, Vitalik publicou um novo artigo intitulado "Memory access is O(N^(1/3))", explorando a complexidade do acesso à memória. Ele discutiu a questão da complexidade do "acesso à memória" em estruturas de dados e algoritmos, sugerindo que, sob certas arquiteturas ou modelos, o custo de acessar a memória pode ter um limite superior de O(N^(1/3)). Vitalik destacou que a complexidade de tempo dos algoritmos clássicos de ordenação é O(N log N), mas ao considerar o gargalo do acesso à memória, é necessário reavaliar a análise de eficiência para conjuntos de dados em larga escala. Este tema é inspirador para o design de sistemas de base de blockchain, especialmente ao lidar com grandes volumes de estado, sincronização de nós e mecanismos de disponibilidade de dados (DA / amostragem de disponibilidade de dados, etc.), onde é preciso considerar com cautela o gargalo de eficiência no "acesso à memória".