Como recordarán, en noviembre del año pasado anunciamos una beca para estudiar los Autómatas Celulares y la Optimización de Autopeering. Ese trabajo ya ha sido completado por nuestros destacados becarios, y este post contiene un resumen de la investigación y sus conclusiones.
Aunque el resultado no fue positivo para la inclusión de los Autómatas Celulares (AC) en futuras actualizaciones del protocolo IOTA, la investigación condujo a nuevos conocimientos que nos ayudaron con otros aspectos de Coordicide. También subraya la importancia de realizar una investigación rigurosa necesaria para abordar los problemas difíciles de nuestro equipo. Esta investigación es un magnífico ejemplo de aventurarse en lo desconocido, y como parte necesaria para entender lo que funciona, lo que no funciona y por qué. Sólo adentrándose en territorio desconocido nos podemos encontrar con aspectos inesperados que pueden resultar muy beneficiosos.
Estamos agradecidos por los conocimientos adquiridos en esta investigación. También estamos agradecidos por los resultados positivos de la investigación, que incluyen una propuesta de modificación del protocolo de votación, y también una implementación para el algoritmo de autopeering de ar-row. Muchas gracias a Radosław Michalski, Daria Dziubałtowska y Piotr Macek por su excelente y exhaustivo trabajo, y por el texto que sigue.
Introducción a la investigación
El objetivo de nuestro proyecto de investigación era analizar el impacto de las configuraciones del grafo en la consecución del consenso para el algoritmo CA. Para ello, dentro del proyecto analizamos las propiedades estructurales de los grafos generados por los métodos de autopeering ar-row y salt-based, es decir, los métodos para establecer enlaces entre los nodos de IOTA. En segundo lugar, pasamos a estudiar el impacto de las configuraciones de los grafos, concretamente en lo que respecta a cómo el consenso basado en Autómatas Celulares alcanza la estabilidad y, en caso contrario, cómo superar estas situaciones. Basándonos en los resultados de estos dos análisis, también propusimos modificaciones en el protocolo de votación para evitar situaciones de metaestabilidad que resulten en opiniones divididas sobre el estado del ledger. Por último, implementamos un módulo de GoShimmer para el algoritmo de autopeering de ar-row. En este blog presentamos los resultados de la investigación.
En primer lugar, nos gustaría remitir a los lectores a otra entrada del blog que introduce la idea del consenso en la Tangle, en la que se puede encontrar una descripción más fundamental del consenso y múltiples estrategias para maximizar las posibilidades de alcanzarlo. En nuestro proyecto de investigación nos centramos en el consenso celular que también se menciona allí. Para más detalles, consulta la sección 6.2 del Whitepaper acerca del Coordicide.
Algoritmos de Autopeering
El objetivo de esta parte de la investigación era evaluar dos algoritmos de autopeering: el basado en el algoritmo sal y el basado en ar-row. Cada uno de estos dos métodos tiene diferentes medios para crear una estructura de grafos y difieren en la forma en que los nodos se comunican entre sí para encontrar compañeros. Lo ideal es que ambos métodos terminen con grafos k-regulares, es decir, grafos en los que cada vértice está conectado a k vecinos. Estos grafos se utilizaron posteriormente para ejecutar el algoritmo de Autómatas Celulares para alcanzar el consenso. Sin embargo, antes de hacerlo, queríamos evaluar si los grafos generados por los algoritmos basados en Sal y en ar-row difieren estructuralmente.
Ejecutamos estos métodos para un número seleccionado de combinaciones <n, k>, donde n representa el número de vértices, para múltiples instancias de grafos (en total analizamos 2.916.670 grafos). Para el método basado en sal, limitamos el número de rondas a cien, ya que en la mayoría de los casos, si los grafos no convergen a la regularidad k en cien rondas, tampoco convergen en un número mayor de rondas.
De esta parte de la investigación se pueden extraer varias conclusiones
- Para el algoritmo ar-row, es posible alcanzar la k-regularidad en dos de cada tres casos
- Para el método basado en sal, es difícil alcanzar la k-regularidad, pero el número medio de aristas y su varianza son, al menos desde nuestra perspectiva, aceptables y cercanos a la k-regularidad
- ar-row es un método que, debido a su naturaleza, genera grafos un orden de magnitud más rápido que el algoritmo basado en sal
- las medidas grafos globales de los grafos generados (k-regularidad, modularidad, tamaño de la circunferencia y diámetro) revelan una gran similitud entre los dos métodos, que ha sido evaluada estadísticamente
- las medidas de los grafos locales (coeficiente de agrupación y entrecruzamiento) sólo divergen ligeramente; las diferencias entre las distribuciones se han cuantificado mediante la medida de divergencia de Kullback-Leibler
Consenso de Autómatas Celulares
Como segundo paso, implementamos el algoritmo de Autómatas Celulares basado en la descripción presentada en el mencionado whitepaper. Los nodos determinaban su propia opinión basándose en la opinión de sus vecinos de la ronda anterior. En nuestra implementación nos desviamos en un aspecto de la versión presentada en el documento Coordicide: Cuando ninguna opinión tenía la mayoría, no utilizamos un estado de indecisión. En su lugar, el nodo cambia su opinión por la opuesta que tenía en la ronda anterior. Probamos el algoritmo CA en gráficos con diferentes combinaciones de <n, k>. Para todas nuestras simulaciones utilizamos un número de rondas M=100, el número de rondas consecutivas con la misma opinión para que un nodo se convierta en definitivo l=4, y utilizamos la función lineal como función monótona para castigar a los nodos que tienen menos de k vecinos.
La parte más importante de esta investigación fue contar el número de situaciones metaestables que se produjeron durante la simulación de CA. Como extracto de todos los resultados que tenemos, en la Figura 1 y en la Figura 2 presentamos cómo la metaestabilidad depende de k y n (para las filas de sal y de ar, respectivamente).
Antes de seguir adelante, vamos a resumir las conclusiones que se pueden extraer del análisis de la AC con temperatura cero:
- en general, el porcentaje de situaciones metaestables superó nuestras expectativas
- para k más pequeños, independientemente de n, alcanzar el consenso es más difícil
se observa una diferencia para los gráficos subyacentes basados en ar-row y en salt en cuanto al porcentaje de situaciones metaestables para CA (independientemente del método de asignación de estados iniciales), pero no hay un claro ganador - el algoritmo gossip da lugar a menos situaciones metaestables para un n mayor, en comparación con los nodos iniciales con opiniones aleatorias
- los experimentos realizados no han proporcionado suficientes datos para realizar la estimación de los casos metaestables para n más grandes
Mejora de la AC con temperatura cero
Los resultados del AC con temperatura cero no fueron lo suficientemente buenos, así que analizamos manualmente algunas situaciones metaestables para grafos pequeños para intentar averiguar por qué el algoritmo no lograba alcanzar el consenso y señalamos dos puntos cruciales que dificultan que la red entre en un estado estable.
El primer problema que observamos es cuando algunos nodos cambian de opinión cuando las opiniones de su vecindario estaban divididas al 50%. Esto hacía que algunos nodos cambiaran de opinión en cada ronda, lo que en consecuencia provocaba que otros nodos cambiaran de opinión en rondas consecutivas y no permitía que el estado se estabilizara.
Para las pruebas, cambiamos esto de forma que en las situaciones descritas el nodo cambiara su opinión de forma aleatoria, por lo que o bien se quedaba con su opinión actual o la cambiaba. Esto mejoró los resultados en el caso de los gráficos pequeños, pero en el caso de los gráficos grandes (con 100 nodos), esto empeoró los resultados y abandonamos este cambio.
El segundo problema que encontramos fue que algunos nodos cambiaban de opinión en cada ronda de ida y vuelta, lo que provocaba que algunos de sus vecinos también cambiaran de opinión en rondas consecutivas, no dejando que la red se estabilizara.
Como el problema se produce porque los nodos cambian de opinión en cada ronda, decidimos aplicar un cambio que permite a los nodos cambiar de opinión en dos rondas consecutivas sólo con una pequeña probabilidad y con probabilidad cero. A partir del análisis de un pequeño subconjunto de gráficos grandes y pequeños, permitir que los nodos cambien de opinión en dos rondas consecutivas con un 10% de probabilidad dio los mejores resultados.
Las modificaciones descritas mejoraron mucho los resultados, aunque a veces siguen produciéndose situaciones metaestables. Las investigaciones posteriores no nos condujeron a más mejoras, ya que las situaciones metaestables restantes siguen siendo causadas por los nodos que cambian de opinión una y otra vez. Esos casos metaestables restantes en nuestro simulador son lo suficientemente desafortunados como para que, a pesar del 10% de probabilidad de que los nodos cambien de opinión en dos rondas consecutivas, algunos nodos cambien de opinión en cada ronda. No pudimos encontrar una solución lo suficientemente buena como para cubrir todos los casos, pero los cambios descritos proporcionaron una gran mejora.
Como demuestran los resultados (véase la figura 3), el número de situaciones metaestables disminuyó significativamente. En este caso, los gráficos basados en ar-row superaron a los basados en sal, pero los avances se observaron claramente para ambas familias. Esto demuestra que hay margen de mejora incluso sin las temperaturas introducidas en el sistema
¡Gracias por leer! Esperamos que sigas nuestras actualizaciones en los blogs, y también eres bienvenido a contactar con los miembros del equipo de investigación en el canal #tanglemath de nuestro Discord. También eres bienvenido a seguir y participar en nuestras discusiones técnicas en nuestro foro público: IOTA.cafe.
