What is a Directed Acyclic Graph (DAG): Blockchain vs. DAG
Key Questions Answered
Several crypto protocols have been dubbed ‘Ethereum Killers’ but have seen limited tangible success. Similarly, DAGs or Directed Acyclic Graphs are sometimes called the “Blockchain Killer”.
Diving deep into DAGs from a technical standpoint is required to understand their approach, utilities, and potential. Simply put, DAGs are a data structure model that allows for concurrent development without compromising on the integrity of the data or its iterations. The DAGs model replaces the linear history model which fails to consider loops and feedback provided at different stages.
What is a Directed Acyclic Graph?
A DAG is a graph that represents a series of activities and the flow from one activity to another. The activities are depicted as circles (vertex), and the order in which the activities were done are represented using lines (edge) with unidirectional arrows. The DAG model is super flexible and allows developers to express themselves.
The vertices and edges essentially form the core of DAGs, similar to how blocks work in the blockchain. Also, similar to the minting of blocks, transactions are added to the network by referencing the previous transactions.
How Does a Directed Acyclic Graph Work?
Imagine Dan and Glenn are working on a travel itinerary to Budapest on Google Docs. Here, Dan is typing the data under three subheadings i.e. Place, distance, and time required. Glenn updates the document with pictures of all the places they should consider adding to the itinerary. They are adding information and editing at different times.
Now, in a linear history model, Dan would not be able to go back in time, grab his version of the document, and continue typing. Why? Because, in the linear model, changes can only be made to the most recent version of the depository. But, in a DAG model, Dan could take a copy of the earlier version and continue typing the data.
The key takeaway to note is the last version on which Dan is typing shall be recorded with arrows pointing towards Dan’s first version, representing the flow of activity and edits.
How to Check if a Directed Graph is Acyclic?
A graph is said to be acyclic when the graph –
- Has zero nodes,
- Has leafs,
- Can be sorted topologically.
To tests the graph for being acyclic or not, there are certain toolings available –
- Kahn algorithmto check the presence of nodes,
- Tarjan algorithmto test connection i.e. presence of node leafs,
- DFS or Depth First Search.
Applications of Directed Acyclic Graphs
Businesses use DAG-enabled workflow management software to plan, organize, and schedule their processes. Each process has a list of tasks that combine to form DAGs. Here, every vertex is an activity that needs to be completed. On a priority front, edges reflect the action that needs to be taken before moving on to the next activity.
Recording transactions is user-friendly with DAGs, more so than with conventional blockchain networks equipped with proof of work or proof of stake consensus mechanisms. Due to their graph structure, they are often more efficient than blockchain technology.
Data Processing Networks
From recording data to aggregating them, the entire data pipeline adopts the DAG model. This provides them an extra cushion of comfort as the DAG model recognizes multiple paths in the flow of the critical path. Also, concurrent working on solutions is made possible as parallel processes can start as soon as the inputs are provided.
Blockchain vs Directed Acyclic Graphs
Blockchain tech and DAGs record transactions on a distributed ledger using different mechanisms. While the former uses blocks and decentralized validation to authenticate transactions, the latter uses the previous transaction as proof to provide validation. This means there is no absolute requirement for miners or validators i.e. no or minimal gas fees required.
The infrastructure of DAGs allows them to scale at ease and yet facilitate the conduct of transactions. While blockchain networks have failed to scale efficiently, they have achieved decentralization in their operations as the concept of authority is eliminated. However, DAGs are, to date, centralized to a fair extent with private network systems.
With better adoption of DAGs, they can manage high volumes of transactions at minimal power consumption and need for hardware.
DAGs are at a nascent stage in development. While the potential is present, the feasibility and scalability has yet to be realized. Also, the time required for developers to adopt DAGs as the core of dApp or product shall be the critical factor. As the journey towards Web3 starts to gain pace, DAGs might be the very stimulant the blockchain industry requires.