Konsequent vorwärts Was ist ein Directed Acyclic Graph (DAG)?

Anbieter zum Thema

Schneider Electric GmbH

Fsas Technologies GmbH

EPS Rechenzentrum Infrastruktur GmbH

Die Welt der Mathematik liegt im Hintergrund algorithmischer Prozesse. Aus dieser stammt der Begriff Directed Acyclic Graph (DAG).

Directed Acyclic Graph (DAG) heißt zu deutsch gerichteter azyklischer Graph. Um den Begriff zu verstehen, beschäftigt man sich am besten zunächst mit seinen Bestandteilen.

Ein Graph ist ein mathematisches Gebilde aus Kanten (Edges) und Knoten (Nodes). Die Knoten werden durch Kanten verbunden.

Graphen stellen Relationen dar

Graphen werden beispielsweise benutzt, um das Verhältnis zweier Dinge zueinander oder die Aktivitäten zwischen zwei Dingen/Personen/Umständen zu beschreiben. Dabei beschreibt die Kante die Art der Relation oder die Aktivität, der Knoten, um welche Dinge/Umstände/Personen es sich handelt.

Dazu ein, zugegeben banales, Beispiel: Stellt ein Knoten einen PC dar und der andere die Stromversorgung, könnte ein Pfeil von der Stromversorgung zu Computer führen, der mit „treibt an“ beschriftet wäre.

Einseitige Beziehung

Können die Kanten aufgrund der logischen Zusammenhänge nur von A nach B führen, nicht aber (mit derselben Qualität) von B nach A, spricht man von gerichteten Graphen. Beispiel: Im Fall von Computer und Stromversorgung als Knoten müsste die Kante mit Spitze auf den Prozessor mit „erhält Energie von“ gekennzeichnet werden, nicht mit „versorgt" wie umgekehrt.

Nähme man dagegen an, das Verhältnis zweier Freunde A und B (Knoten) solle als Graph beschrieben werden, wäre es möglich, das Edge zwischen beiden Knoten in beiden Richtungen mit „ist befreundet mit“ zu beschreiben beziehungsweise einen Pfeil mit Spitzen zu beiden Knoten zu zeichnen, da das Verhältnis von beiden Seiten betrachtet äquivalent ist. Im ersten Fall spricht man von gerichteten (directed), im zweiten von ungerichteten Graphen.

Eine bestimmte Kante weist also nur in eine Richtung. Besteht ein Graph ausschließlich aus solchen Kanten, spricht man vom gerichteten Graph.

Niemals im Kreis herum

Heißt das zu beschreibende Verhältnis zwischen zwei Ereignissen beispielsweise „geschah nach“, dann werden Ereignisse automatisch so geordnet, dass ihre Reihenfolge im Zeitverlauf abgebildet wird, da die Zeit im Standard-Lebensumfeld von Menschen nicht rückwärts läuft.

Gleichzeitig verhindert die Beziehung im letztgenannten Beispiel auch, dass Kanten jemals zu ihrem Ausgangspunkt zurückverweisen: Damit ist der Graph azyklisch. Ein gerichteter azyklischer Graph ist also die grafische Darstellung von Beziehungen oder Aktivitäten mit Akteuren in einer eindeutigen Richtung und ohne die Möglichkeit, diese Richtung umzukehren.

Sparsame Alternative zu Blockchain

DAGs werden unter anderem in neuen algorithmischen Verfahren verwendet, die den ressourcenintensiven Blockchain-Algorithmus ersetzen könnten. Ein solches Verfahren ist Hashgraph. Durch die Möglichkeiten von DAGs ist ihr Rechenaufwand erheblich geringer und die Geschwindigkeit höher bei gleicher oder besserer Sicherheit, da zum Beispiel Hashgraph auch gegen Maschinenfehler („Byzantinische Fehler“) gefeit ist.

Mögliche Anwendungen gleichen denen von Blockchain. Beispiele sind digitale Währungen, digitale Verträge, voll digitalisierte Lieferketten und vieles mehr, wofür man verteilte digitale Hauptbücher (Distributed Digital Ledger) braucht.

(ID:49879079)