Forschungsförderungsbericht –
Zelluläre Automaten Konsens: Konvergenz und Modifikationen
Wie Sie sich vielleicht erinnern, haben wir im November letzten Jahres ein Stipendium für die Untersuchung von Zellulären Automaten und Autopeering-Optimierung angekündigt. Diese Arbeit wurde nun von unseren hervorragenden Stipendiaten abgeschlossen, und dieser Beitrag enthält eine Zusammenfassung der Forschung und ihrer Schlussfolgerungen.
Obwohl das Ergebnis nicht positiv für die Einbeziehung von Cellular Automata (CA) in zukünftige Upgrades des IOTA-Protokolls war, führte die Forschung zu neuen Erkenntnissen, die uns bei anderen Aspekten von Coordicide helfen. Es unterstreicht auch die Wichtigkeit, die rigorose Forschung zu betreiben, die notwendig ist, um schwierige Probleme anzugehen, die von unserem Team aufgegriffen wurden. Diese Forschung ist ein wunderbares Beispiel dafür, sich ins Unbekannte zu wagen, und zwar als notwendiger Teil des Verständnisses dessen, was funktioniert, was nicht funktioniert, und warum. Nur wenn man sich auf unbekanntes Terrain begibt, kann man über unerwartete Aspekte stolpern, die sich als äußerst nützlich erweisen können.
Wir sind dankbar für die Erkenntnisse, die wir durch diese Forschung gewonnen haben. Wir sind auch dankbar für die positiven Ergebnisse der Forschung, die einen Vorschlag für Modifikationen des Abstimmungsprotokolls und auch eine Implementierung für den Ar-Row-Auto-Peering-Algorithmus beinhalten. Vielen Dank an Radosław Michalski, Daria Dziubałtowska und Piotr Macek für ihre ausgezeichnete und gründliche Arbeit und für den folgenden Text!
Einführung in die Forschung
Das Ziel unseres Forschungsprojekts war es, den Einfluss von Graphenkonfigurationen auf die Konsensfindung für den CA-Algorithmus zu analysieren. Um dies zu tun, analysierten wir im Rahmen des Projekts die strukturellen Eigenschaften von Graphen, die durch die Ar-Row- und Salt-basierten Autopeering-Methoden erzeugt wurden, d.h. die Methoden zur Herstellung von Verbindungen zwischen IOTA-Knoten. Zweitens gingen wir dazu über, die Auswirkungen von Graphenkonfigurationen zu untersuchen, insbesondere im Hinblick darauf, wie der auf zellulären Automaten basierende Konsens Stabilität erreicht und, falls nicht, wie man diese Situationen überwinden kann. Basierend auf den Ergebnissen dieser beiden Analysen schlugen wir auch Änderungen am Abstimmungsprotokoll vor, um metastabile Situationen zu vermeiden, die zu geteilten Meinungen über den Ledger-Status führen. Zu guter Letzt haben wir ein GoShimmer-Modul für den Ar-Row-Auto-Peering-Algorithmus implementiert. In diesem Blog-Beitrag werden die Ergebnisse der Forschung vorgestellt.
Zunächst möchten wir die Leser auf einen anderen Blog-Beitrag verweisen, der in die Idee des Konsens im Tangle einführt – darin finden Sie eine grundlegendere Beschreibung des Konsens und mehrere Strategien zur Maximierung der Chancen, ihn zu erreichen. In unserem Forschungsprojekt haben wir uns auf den dort ebenfalls erwähnten zellulären Konsens konzentriert. Weitere Details finden Sie in Abschnitt 6.2 des Coordicide White Paper.
Autopeering-Algorithmen
- für den Ar-Row-Algorithmus ist das Erreichen von k-Regelmäßigkeit in zwei von drei Fällen möglich
- für die salzbasierte Methode ist das Erreichen der k-Regelmäßigkeit schwer zu erreichen, aber die mittlere Anzahl der Kanten und ihre Varianz sind, zumindest aus unserer Sicht, akzeptabel und nahe an der k-Regelmäßigkeit
- ar-row ist eine Methode, die aufgrund ihrer Natur Graphen um eine Größenordnung schneller erzeugt als der Salt-basierte Algorithmus
- globale Graphenmaße der generierten Graphen (k-Regelmäßigkeit, Modularität, Umfangsgröße und Durchmesser) zeigen eine hohe Ähnlichkeit zwischen beiden Methoden, die statistisch ausgewertet wurde
- Lokale Graphenmaße (Clustering-Koeffizient und Betweenness) divergieren nur geringfügig – die Unterschiede zwischen den Verteilungen wurden mit Hilfe des Kullback-Leibler-Divergenzmaßes quantifiziert
Cellular Automata-Konsens
In einem zweiten Schritt implementierten wir den Cellular Automata-Algorithmus, der auf der Beschreibung aus dem oben genannten White Paper basiert. Die Knoten ermittelten ihre eigene Meinung basierend auf der Meinung ihrer Nachbarn aus der vorherigen Runde. In unserer Implementierung wichen wir in einem Aspekt von der im Coordicide-Paper vorgestellten Version ab: Wenn keine Meinung die Mehrheit hatte, haben wir keinen unentschiedenen Zustand verwendet. Stattdessen ändert der Knoten seine Meinung zu der entgegengesetzten, die er in der vorherigen Runde hatte. Wir haben den CA-Algorithmus auf Graphen mit verschiedenen <n, k>-Kombinationen getestet. Für alle unsere Simulationen verwendeten wir eine Anzahl von Runden M=100, die Anzahl der aufeinanderfolgenden Runden mit der gleichen Meinung für einen Knoten, um endgültig zu werden l=4, und wir verwendeten eine lineare Funktion als monotone Funktion für die Bestrafung von Knoten, die weniger als k Nachbarn haben.
Der wichtigste Teil dieser Untersuchung bestand darin, die Anzahl der metastabilen Situationen zu zählen, die während der CA-Simulation auftraten. Als Auszug aus allen Ergebnissen, die wir haben, stellen wir in Abbildung 1 und Abbildung 2 dar, wie die Metastabilität von k und n abhängt (für salzbasierte bzw. ar-row).
Bevor wir weitergehen, lassen Sie uns zusammenfassen, welche Schlussfolgerungen für die Analyse von CA mit Nulltemperatur gezogen werden können:
im Allgemeinen übertrifft der Prozentsatz der metastabilen Situationen unsere Erwartungen
für kleinere k, unabhängig von n, ist es schwieriger, den Konsens zu erreichen
es gibt einen Unterschied zwischen Arrow- und Salt-basierten zugrundeliegenden Graphen in Bezug auf den Prozentsatz metastabiler Situationen für CA (unabhängig von der Methode der Zuweisung von Anfangszuständen), aber es gibt keinen klaren Gewinner
der Gossip-Algorithmus führt zu weniger metastabilen Situationen für höhere n, im Vergleich zu initiierenden Knoten mit zufälligen Meinungen
die durchgeführten Experimente haben nicht genügend Daten geliefert, um die Abschätzung der metastabilen Fälle für größere n durchzuführen
Verbesserte CA mit Null-Temperatur
Die Ergebnisse für CA mit Null-Temperatur waren nicht ausreichend gut, daher haben wir einige metastabile Situationen für kleine Graphen manuell analysiert, um herauszufinden, warum der Algorithmus keinen Konsens erreichen konnte, und wir haben zwei entscheidende Punkte ausgemacht, die es dem Netzwerk schwer machen, in einen stabilen Zustand zu gelangen.
Das erste Problem, das uns aufgefallen ist, ist, dass einige Knoten ihre Meinung ändern, wenn die Meinungen ihrer Nachbarn 50/50 geteilt waren. Dies führte dazu, dass einige Knoten in jeder Runde ihre Meinung änderten, was wiederum dazu führte, dass andere Knoten in aufeinanderfolgenden Runden ihre Meinung änderten und der Zustand sich nicht stabilisieren konnte.
Zum Testen änderten wir dies so, dass der Knoten in den beschriebenen Situationen seine Meinung zufällig ändert, also entweder bei seiner aktuellen Meinung bleibt oder sie ändert. Dadurch wurden die Ergebnisse bei kleinen Graphen besser, bei großen Graphen (mit 100 Knoten) stellte sich jedoch heraus, dass dies die Ergebnisse verschlechterte und wir ließen diese Änderung fallen.
Die zweite Herausforderung, die wir feststellten, war, dass einige Knoten in jeder Runde ihre Meinung hin und her wechselten, was dazu führte, dass einige ihrer Nachbarn in aufeinanderfolgenden Runden ebenfalls ihre Meinung änderten, wodurch sich das Netzwerk nicht stabilisieren konnte.
Da das Problem auftritt, weil die Knoten ihre Meinung in jeder Runde ändern, haben wir uns entschieden, eine Änderung anzuwenden, die es den Knoten erlaubt, ihre Meinung in zwei aufeinanderfolgenden Runden nur mit einer geringen Wahrscheinlichkeit und mit einer Wahrscheinlichkeit von Null zu ändern. Die Analyse einer kleinen Teilmenge von großen und kleinen Graphen ergab, dass die besten Ergebnisse erzielt wurden, wenn man den Knoten erlaubte, ihre Meinung in zwei aufeinanderfolgenden Runden mit einer Wahrscheinlichkeit von 10 % zu ändern.
Die beschriebenen Modifikationen verbesserten die Ergebnisse erheblich, dennoch treten manchmal immer noch metastabile Situationen auf. Weitere Untersuchungen führten nicht zu weiteren Verbesserungen, da die verbleibenden metastabilen Situationen immer noch durch Knoten verursacht werden, die ihre Meinung hin und her wechseln. Diese verbleibenden metastabilen Fälle in unserem Simulator sind so unglücklich, dass trotz einer Wahrscheinlichkeit von 10 %, dass Knoten ihre Meinung in zwei aufeinanderfolgenden Runden ändern, einige Knoten ihre Meinung in jeder Runde ändern. Wir waren nicht in der Lage, eine Lösung zu finden, die gut genug ist, um alle Fälle abzudecken, aber die beschriebenen Änderungen brachten eine große Verbesserung.
Wie die Ergebnisse zeigen (siehe Abbildung 3), sank die Anzahl der metastabilen Situationen
deutlich. In diesem Fall übertrafen die Arrow-basierten Graphen die Salt-basierten, aber die Fortschritte waren bei beiden Familien deutlich zu beobachten. Dies zeigt, dass es auch ohne die in das System eingeführten Temperaturen Raum für Verbesserungen gibt
Danke fürs Lesen! Wir hoffen, dass Sie weiterhin unsere Updates hier im Blog verfolgen. Sie sind auch herzlich eingeladen, sich mit Mitgliedern des Forschungsteams im Channel #tanglemath auf unserem Discord zu verbinden. Sie sind auch herzlich eingeladen, unsere technischen Diskussionen in unserem öffentlichen Forum zu verfolgen und daran teilzunehmen: IOTA.cafe.
Original by IOTA Foundation: https://blog.iota.org/research-grant-report-cellular-automata-consensus-convergence-and-modifications/
Schreibe einen Kommentar