Klatschprotokoll – Wikipedia

EIN Klatschprotokoll ist ein Verfahren oder ein Prozess der Computer-Peer-to-Peer-Kommunikation, das auf der Ausbreitung von Epidemien basiert.^[1] Einige verteilte Systeme verwenden Peer-to-Peer-Klatsch, um sicherzustellen, dass Daten an alle Mitglieder einer Gruppe weitergegeben werden. Einige Ad-hoc-Netzwerke haben keine zentrale Registrierung. Die einzige Möglichkeit, gemeinsame Daten zu verbreiten, besteht darin, sich darauf zu verlassen, dass jedes Mitglied diese an seine Nachbarn weitergibt.

Der Begriff Epidemieprotokoll wird manchmal als Synonym für ein Klatschprotokoll verwendet, da Klatsch Informationen auf ähnliche Weise verbreitet wie die Verbreitung eines Virus in einer biologischen Gemeinschaft.

Klatschkommunikation[edit]

Das Konzept von Klatschkommunikation kann durch die Analogie von Büroangestellten veranschaulicht werden, die Gerüchte verbreiten. Nehmen wir an, die Büroangestellten versammeln sich jede Stunde um den Wasserkühler. Jeder Mitarbeiter paart sich mit einem anderen, wird nach dem Zufallsprinzip ausgewählt und teilt den neuesten Klatsch. Zu Beginn des Tages beginnt Dave ein neues Gerücht: Er kommentiert Bob, dass er glaubt, dass Charlie seinen Schnurrbart färbt. Beim nächsten Treffen erzählt Bob Alice, während Dave Eve die Idee wiederholt. Nach jedem Rendezvous mit dem Wasserkühler verdoppelt sich die Anzahl der Personen, die das Gerücht gehört haben, ungefähr (obwohl dies nicht das zweimalige Klatschen mit derselben Person erklärt; vielleicht versucht Dave, Frank die Geschichte zu erzählen, nur um festzustellen, dass Frank sie bereits gehört hat von Alice). Computersysteme implementieren diese Art von Protokoll normalerweise mit einer Form der zufälligen “Peer-Auswahl”: Mit einer bestimmten Häufigkeit wählt jede Maschine zufällig eine andere Maschine aus und teilt alle heißen Gerüchte.

Das Problem mit dem Begriff “Klatsch” ist, dass die Qualität des Dienstes (dh die vollständige und rechtzeitige Verbreitung) auf der Anforderung beruht, dass jedes Mitglied nicht diskriminiert und eine schnelle und zuverlässige Übertragung der Daten an jedes Mitglied seines eigenen Peer-Netzwerks sicherstellt. In einem echten Büroklatschszenario ist nicht jeder mit dem Klatsch vertraut, der verbreitet wird. Klatsch und Tratsch sind diskriminierend und oft werden die Teilnehmer von wichtigen oder wichtigen Kommunikationen ausgeschlossen. Daher ist der Vergleich mit „Büroklatsch“ nicht so gut wie der Vergleich mit der Ausbreitung einer Epidemie. Trotzdem wird die Technik der Peer-to-Peer-Kommunikation manchmal als “Klatsch” bezeichnet.

Viele Varianten und Stile[edit]

Es gibt wahrscheinlich Hunderte von Varianten spezifischer Gossip-ähnlicher Protokolle, da jedes Verwendungsszenario wahrscheinlich an die spezifischen Anforderungen des Unternehmens angepasst wird.

Zum Beispiel könnte ein Klatschprotokoll einige dieser Ideen verwenden:

• Der Kern des Protokolls besteht aus periodischen, paarweisen Interaktionen zwischen Prozessen.
• Die während dieser Interaktionen ausgetauschten Informationen sind von begrenzter Größe.
• Wenn Agenten interagieren, ändert sich der Status mindestens eines Agenten, um den Status des anderen widerzuspiegeln.
• Eine zuverlässige Kommunikation wird nicht vorausgesetzt.
• Die Häufigkeit der Interaktionen ist im Vergleich zu typischen Nachrichtenlatenzen gering, so dass die Protokollkosten vernachlässigbar sind.
• Es gibt irgendeine Form von Zufälligkeit bei der Peer-Auswahl. Peers können aus dem vollständigen Satz von Knoten oder aus einem kleineren Satz von Nachbarn ausgewählt werden.
• Aufgrund der Replikation besteht eine implizite Redundanz der gelieferten Informationen.

Klatschprotokolltypen[edit]

Es ist nützlich, zwei vorherrschende Arten von Klatschprotokollen zu unterscheiden:^[2]

• Verbreitungsprotokolle (oder Gerüchte-Protokolle). Diese verwenden Klatsch, um Informationen zu verbreiten; Sie arbeiten im Wesentlichen mit Flutungsagenten im Netzwerk, jedoch auf eine Weise, die begrenzte Worst-Case-Lasten erzeugt:
  1. Protokolle zur Ereignisverbreitung Verwenden Sie Klatsch, um Multicasts durchzuführen. Sie melden Ereignisse, aber der Klatsch tritt regelmäßig auf und Ereignisse lösen den Klatsch nicht wirklich aus. Ein Problem hierbei ist die potenziell hohe Latenz vom Eintreten des Ereignisses bis zur Auslieferung.
  2. Protokolle zur Verbreitung von Hintergrunddaten Klatschen Sie ständig über Informationen, die den teilnehmenden Knoten zugeordnet sind. In der Regel ist die Ausbreitungslatenz kein Problem, möglicherweise weil sich die fraglichen Informationen langsam ändern oder es keine signifikante Strafe für das Eingreifen in leicht veraltete Daten gibt.
• Protokolle, die Aggregate berechnen. Diese berechnen ein netzwerkweites Aggregat, indem sie Informationen an den Knoten im Netzwerk abtasten und die Werte kombinieren, um einen systemweiten Wert zu erhalten – der größte Wert, den einige Messknoten machen, der kleinste usw. Die Hauptanforderung ist, dass das Aggregat muss durch paarweisen Informationsaustausch fester Größe berechenbar sein; Diese enden in der Regel nach einer Reihe von logarithmischen Runden des Informationsaustauschs in der Systemgröße. Zu diesem Zeitpunkt ist ein umfassendes Informationsflussmuster erstellt worden. Als Nebeneffekt der Aggregation ist es möglich, andere Arten von Problemen mit Klatsch und Tratsch zu lösen. Beispielsweise gibt es Klatschprotokolle, mit denen die Knoten in einer Klatschüberlagerung in einer nach logarithmischer Zeit nach Knoten-ID (oder einem anderen Attribut) sortierten Liste mithilfe eines aggregationsartigen Informationsaustauschs in einer Liste angeordnet werden können. In ähnlicher Weise gibt es Klatschalgorithmen, die Knoten in einem Baum anordnen und Aggregate wie “Summe” oder “Anzahl” berechnen, indem sie in einem Muster klatschen, das voreingenommen ist, um mit der Baumstruktur übereinzustimmen.

Viele Protokolle, die vor der frühesten Verwendung des Begriffs “Klatsch” entstanden sind, fallen unter diese eher umfassende Definition. Beispielsweise verwenden Internet-Routing-Protokolle häufig einen klatschartigen Informationsaustausch. Ein Klatschsubstrat kann verwendet werden, um ein geroutetes Standardnetzwerk zu implementieren: Knoten “klatschen” über herkömmliche Punkt-zu-Punkt-Nachrichten und leiten den Verkehr effektiv durch die Klatschschicht. Wenn die Bandbreite dies zulässt, bedeutet dies, dass ein Klatschsystem möglicherweise jedes klassische Protokoll unterstützen oder jeden klassischen verteilten Dienst implementieren kann. Eine derart weit gefasste Auslegung ist jedoch selten beabsichtigt. Typischer sind Klatschprotokolle, die spezifisch regelmäßig, periodisch, relativ faul, symmetrisch und dezentral ausgeführt werden. Besonders charakteristisch ist der hohe Symmetriegrad zwischen den Knoten. Während man also ein 2-Phasen-Festschreibungsprotokoll über ein Klatschsubstrat ausführen könnte, würde dies im Widerspruch zum Geist, wenn nicht zum Wortlaut der Definition stehen.

Der Begriff konvergent konsistent wird manchmal verwendet, um Protokolle zu beschreiben, die eine exponentiell schnelle Verbreitung von Informationen erreichen. Zu diesem Zweck muss ein Protokoll alle neuen Informationen an alle Knoten weitergeben, die von den Informationen innerhalb der logarithmischen Zeit in der Größe des Systems betroffen sind (die “Mischzeit” muss in der Systemgröße logarithmisch sein).

Beispiele[edit]

Angenommen, wir möchten das Objekt finden, das einem Suchmuster in einem Netzwerk unbekannter Größe am ehesten entspricht, in dem jedoch die Computer miteinander verbunden sind und auf dem auf jedem Computer ein kleiner Computer ausgeführt wird Agent Programm, das ein Klatschprotokoll implementiert.

• Um die Suche zu starten, bittet ein Benutzer den lokalen Agenten, über die Suchzeichenfolge zu klatschen. (Wir gehen davon aus, dass Agenten entweder mit einer bekannten Liste von Peers beginnen oder diese Informationen aus einer Art gemeinsam genutztem Geschäft abrufen.)
• In regelmäßigen Abständen (zur Vereinfachung beispielsweise zehnmal pro Sekunde) wählt jeder Agent nach dem Zufallsprinzip einen anderen Agenten aus und klatscht damit. Suchzeichenfolgen, die A bekannt sind, sind jetzt auch B bekannt und umgekehrt. In der nächsten “Runde” des Klatsches werden A und B zusätzliche zufällige Peers auswählen, vielleicht C und D. Dieses Phänomen der runden Verdoppelung macht das Protokoll sehr robust, selbst wenn einige Nachrichten verloren gehen oder einige der ausgewählten Peers es sind das gleiche oder bereits über die Suchzeichenfolge wissen.
• Beim ersten Empfang einer Suchzeichenfolge überprüft jeder Agent seinen lokalen Computer auf übereinstimmende Dokumente.
• Die Agenten klatschen auch über die bisher beste Übereinstimmung. Wenn also A nach der Interaktion mit B klatscht, kennt A die besten Übereinstimmungen, die B bekannt sind, und umgekehrt. Die besten Übereinstimmungen werden sich über das Netzwerk “verbreiten”.

Wenn die Nachrichten möglicherweise groß werden (z. B. wenn viele Suchvorgänge gleichzeitig aktiv sind), sollte eine Größenbeschränkung eingeführt werden. Außerdem sollten Suchvorgänge aus dem Netzwerk “altern”.

Daraus folgt, dass innerhalb der logarithmischen Zeit in der Größe des Netzwerks (der Anzahl der Agenten) jede neue Suchzeichenfolge alle Agenten erreicht hat. Innerhalb einer zusätzlichen Verzögerung derselben ungefähren Länge erfährt jeder Agent, wo die beste Übereinstimmung gefunden werden kann. Insbesondere hat der Agent, der die Suche gestartet hat, die beste Übereinstimmung gefunden.

In einem Netzwerk mit 25.000 Maschinen können wir beispielsweise nach etwa 30 Klatschrunden die beste Übereinstimmung finden: 15, um die Suchzeichenfolge zu verbreiten, und 15 weitere, um die beste Übereinstimmung zu ermitteln. Ein Klatschaustausch kann bis zu einmal in jeder Zehntelsekunde stattfinden, ohne dass eine übermäßige Belastung entsteht. Daher kann diese Form der Netzwerksuche ein großes Rechenzentrum in etwa 3 Sekunden durchsuchen.

In diesem Szenario werden Suchvorgänge möglicherweise nach beispielsweise 10 Sekunden automatisch aus dem Netzwerk entfernt. Bis dahin kennt der Initiator die Antwort und es macht keinen Sinn, weiter über diese Suche zu klatschen.

Klatschprotokolle wurden auch verwendet, um die Konsistenz verteilter Datenbanken oder andere Datentypen in konsistenten Zuständen zu erreichen und aufrechtzuerhalten, die Anzahl der Knoten in einem Netzwerk unbekannter Größe zu zählen, Nachrichten robust zu verbreiten, Knoten gemäß einer Strukturierungsrichtlinie zu organisieren und so zu bauen. Overlay-Netzwerke genannt, Aggregate berechnen, Knoten in einem Netzwerk sortieren, Leiter wählen usw.

Epidemische Algorithmen[edit]

Klatschprotokolle können verwendet werden, um Informationen auf ähnliche Weise zu verbreiten, wie sich eine Virusinfektion in einer biologischen Population ausbreitet. In der Tat wird die Mathematik der Epidemien häufig verwendet, um die Mathematik der Klatschkommunikation zu modellieren. Der Begriff epidemischer Algorithmus wird manchmal verwendet, wenn ein Softwaresystem beschrieben wird, in dem diese Art der klatschbasierten Informationsverbreitung verwendet wird.

Siehe auch[edit]

• Klatschprotokolle sind nur eine Klasse unter vielen Klassen von Netzwerkprotokollen. Siehe auch Virtuelle Synchronität, verteilte Zustandsautomaten, Paxos-Algorithmus, Datenbanktransaktionen. Jede Klasse enthält zehn oder sogar Hunderte von Protokollen, die sich in ihren Details und Leistungseigenschaften unterscheiden, sich jedoch in Bezug auf die den Benutzern angebotenen Garantien ähneln.
• Einige Klatschprotokolle ersetzen den zufälligen Peer-Auswahlmechanismus durch ein deterministischeres Schema. Zum Beispiel in der NeighbourCast Algorithmus, anstatt mit zufälligen Knoten zu sprechen, werden Informationen verbreitet, indem nur mit benachbarten Knoten gesprochen wird. Es gibt eine Reihe von Algorithmen, die ähnliche Ideen verwenden. Eine wichtige Voraussetzung beim Entwerfen solcher Protokolle ist, dass der Nachbarsatz einen Expander-Graphen nachzeichnet.
• Routing
• Tribler, BitTorrent Peer-to-Peer-Client unter Verwendung des Klatschprotokolls.

Verweise[edit]

Hier sind einige zusätzliche Verweise auf aktuelle Arbeiten aus der Klatschgemeinschaft. Das Papier von Demers wird von den meisten Forschern als das erste angesehen, das die Leistungsfähigkeit dieser Protokolle wirklich erkannt und eine formelle Behandlung von Klatsch vorgeschlagen hat.

• Reputationsaggregation im Peer-to-Peer-Netzwerk unter Verwendung des Differential-Gossip-Algorithmus. R. Gupta, YN Singh. CoRR, vol. abs / 1210.4301, 2012.

Obwohl dieses Lehrbuch alt ist, zitieren viele Klatschforscher es als maßgebliche Quelle für Informationen über die mathematische Modellierung von Klatsch- und Epidemieprotokollen:

• Die mathematische Theorie der Epidemien. NJT Bailey, 1957. Griffen Press.