Un grafico aciclico diretto (DAG) è un tipo di grafico in cui è impossibile tornare allo stesso nodo attraversando i bordi.

Nella teoria dei grafi, un grafo è una struttura costituita da nodi collegati da bordi. Puoi pensare ai nodi come punti e ai bordi come linee tracciate da punto a punto.

‘Diretto’ significa che i bordi del grafico si muovono solo in una direzione, dove i bordi futuri dipendono da quelli precedenti. Ad esempio, se si dovesse rappresentare un grafico del processo di cottura e consumo di un pasto composto da riso e pollo, i compiti coinvolti dovrebbero essere ordinati topologicamente (o ordinati topologicamente). Prima di poter mangiare il pasto, è necessario preparare il cibo, in modo che il bordo sarebbe necessariamente diretto dalla preparazione in avanti per mangiare. Ma prima di poter preparare il cibo, è necessario acquistare gli ingredienti, quindi di nuovo il bordo deve passare dall’evento precedente all’evento successivo. Supponendo che il riso sia stato acquistato in un evento separato dal pollo, ci sarebbero due bordi separati per gli eventi di spesa che non sono collegati tra loro, ma che convergono all’evento di preparazione del cibo.

‘Aciclico’ significa che è impossibile iniziare da un punto del grafico e tornare ad esso seguendo i bordi. Mentre un ciclo ritorna al suo punto di partenza originale come un cerchio, un grafico aciclico continua a muoversi in una direzione lineare e non torna mai al punto di partenza. Per continuare con l’esempio precedente di cena di pollo e riso, non è possibile spostarsi sul grafico dall’acquisto del riso alla preparazione del cibo all’acquisto del pollo, poiché ciò richiederebbe lo spostamento all’indietro attraverso il grafico. È impossibile preparare il pollo se non lo hai ancora acquistato.

I DAG sono rappresentazioni grafiche probabilistiche di reti bayesiane che mirano a modellare la dipendenza condizionale (ad esempio, mangiare il pasto dipende dalla preparazione prima).

Diverse criptovalute utilizzano DAG piuttosto che strutture di dati blockchain per elaborare e convalidare le transazioni. Con blockchains, tutti i nodi di una rete si basano sulla stessa singola blockchain con ogni blocco che fa riferimento a quello che lo ha preceduto. Un possibile aspetto negativo di questa struttura è che pone un limite al throughput delle transazioni della rete, poiché ci sono solo così tante transazioni che possono adattarsi a un singolo blocco e solo così tanti blocchi che possono essere convalidati in un dato momento. In una rete DAG, le transazioni sono direttamente collegate tra loro piuttosto che raggruppate in blocchi e le transazioni possono essere elaborate contemporaneamente ad altre. Il risultato è un collo di bottiglia ridotto sul throughput delle transazioni.