Cualquier lista como esta es implícitamente personal; Las cosas que me parecen ingeniosas pueden ser mundanas para otros.
- Saltar listas . Si bien estos son menos importantes prácticamente de lo que desearía que fueran, los encuentro sorprendentes y hermosos; La combinación de algoritmos probabilísticos con lo que efectivamente es un árbol de búsqueda equilibrado inclinado hacia un lado es realmente ingeniosa. Esta es también una contribución relativamente reciente.
- Paxos Resuelve un problema de consecuencias tanto teóricas como prácticas, tanto de manera teórica como prácticamente satisfactoria. También es extraño tratar de entenderlo, incluso para los estándares de los sistemas distribuidos. Se siente un poco como una pintura de Escher; cada objeción que conjures termina resolviéndose ordenadamente, como una mano dibujándose a sí misma. Si bien se descubrió de forma independiente al menos dos veces, fácilmente podría imaginar que no se había descubierto durante décadas más.
- La familia de “máquinas de estado” de algoritmos sin bloqueo . El acceso simultáneo escalable a datos mutables sin bloqueo de sincronización parece imposible cuando se entera por primera vez. Dada una primitiva de comparar e intercambiar, puede razonar sobre estas estructuras utilizando una máquina de estados, donde las flechas son intercambios. Cliff Click ha hecho algunas excelentes presentaciones popularizando este enfoque general, aunque todavía lo asocio más con Maurice Herlihy. Ver, por ejemplo, http://www.azulsystems.com/event…