Directed Acyclic Graphs

Directed acyclic graphs provide developers with new ways to create a web3 world. Time to learn about DAGs!

after reading this, you'll understand:

  • Directed acyclic graphs (DAGs) are good for mapping an efficient process.

  • Hashgraph and other DAGs are a viable replacement for blockchains due to their speed and data-storage capabilities.

  • DAG-based distributed ledgers consume less energy than blockchains.

after reading this, you'll understand:

  • Directed acyclic graphs (DAGs) are good for mapping an efficient process.

  • Hashgraph and other DAGs are a viable replacement for blockchains due to their speed and data-storage capabilities.

  • DAG-based distributed ledgers consume less energy than blockchains.

Directed Acyclic Graphs: A New Direction for Cryptocurrency

Cryptocurrency is typically associated with blockchain technology, but an alternative is rising in popularity. Directed acyclic graph (DAG) technology may be the future of cryptocurrency transactions. Many people are unfamiliar with DAGs and graph theory. If you are a cryptocurrency enthusiast, it is a good idea to learn more about DAGs, how they work, and how they may impact distributed ledger technology.

What is a directed acyclic graph?

Graphs consist of vertices and edges. In a traditional graph, edges connect pairs of vertices, or points, and have no defined direction. In directed acyclic graphs, the edges indicate directed path from one vertex to the next and the edges never lead back to a vertex to form a loop.

To say a graph is "directed" means the edges have defined directions, and "acyclic graph" means there are no feedback loops.

These directed graphs have many uses, ranging from family trees to cryptocurrency. These directional graphs are often used for spreadsheet formulas involving multiple cells with causal relationships. For example, if the value of cell A1 is dependent on the value of cell B2, and B2 is dependent on the value of two other cells, the spreadsheet must update those values in a specific order; in this case, a DAG is used to ensure the cells are updated correctly.

To help get a grip on directed acyclic graphs, let's look at some of the basic terms.

Key elements and concepts

Vertex

A vertex is a circle or point that represents an event or activity. In a DAG, an edge, or line, connects one vertex to another to indicate a logical order for a process.

Edge

Edges are the connections formed between two vertices. In DAGs, the edge of two vertices is represented by a line with an arrow at one end. The arrow indicates that one vertex must occur before the vertex being pointed to can occur. DAG edges indicate the direction of the graph. The vertices all point in the same direction, away from the first vertex.

Topological sorting

Topological sorting is the linear ordering of a DAG where every edge marks the end of one vertex and the beginning of another. This topological ordering is essential in computer science as it dictates that each node may be visited only after prior dependencies are completed.

In many ways, topological sorting is a type of schedule that ensures tasks are completed in a specific order. If, for example, you designed a cryptocurrency raffle tool, it would likely require a random number to be generated before a winner was awarded any tokens. A DAG illustrating the raffle process would include a vertex for random number generation with at least one edge pointing toward a vertex for awarding tokens.

Transitive closure and transitive reduction

Transitive closure is one of the concepts that separate directional acyclic graphs from a blockchain structure. When a transitive closure is constructed in a DAG, it may allow programs to reach nodes in fewer steps.

For example, if your program has four nodes and a linear structure, it could be assumed that you could only reach node four by starting at node one, followed by node two, node three, and then node four. However, a transitive closure could determine that you could jump straight from node one to node four.

A transitive reduction produces a graph with the fewest possible edges. The transitive reduction method is a helpful way to create DAGs from a partially ordered set.

Causal inference

Causal inference is the process of inferring that something is likely to be the cause of something else. For example, if you find food crumbs on your carpet, you could assume that was likely caused by someone eating.

Causal inference is often accomplished by analyzing responses of effect variables when the cause of the variable is altered.

Causal effect and causal relationships

A causal effect is when something happens because of something else that occurred. For example, a tower of Jenga blocks falls over when you remove an essential supporting block. Causal effect is an important element of DAGs, as each node may influence the way the following node works.

Causal relationships exist when one variable directly influences another. For example, each block you remove from a Jenga tower has a potential causal relationship with the tower falling over.

Causal diagrams

These diagrams represent causal relationships within a system. A directed graph can be a type of causal diagram.

Instrumental variables

Instrumental variables can help determine causal relationships when controlled experiments aren't practical. When trying to determine the causal effect of one variable (variable X) on another (variable Y), an instrumental variable is a third variable (variable Z) that can impact X via its effect on Y or vice versa.

Observational data

Observational data is data collected based on the observation of a particular subject where the subject doesn't have to be directly involved in the data collection process. DAGs can be an excellent tool for mapping the causal effect of observational data.

DAG and distributed ledger technology

Distributed ledgers like Hedera can use DAGs in numerous ways. For example, Hedera's gossip protocol involves nodes communicating with each other about any and all new information they learn. Of course, agreement among nodes is fundamental to a distributed ledger and the replacement of a central validating authority. For instance, if one node becomes aware of new information, it will share it with a random node. That first node and the randomly chosen node then share that information with two other randomly chosen nodes that do the same. This process continues until every node is aware of the new information. And in this way, consensus is reached.

Each node commemorates this sharing of new information with an event — a cryptocurrency transaction, for example. The history of these information-sharing events is referred to as gossip about gossip. The gossip about gossip history is represented as a type of DAG known as hashgraph.

DAGs like hashgraph are seen as a viable replacement for traditional blockchains due to their speed and data-storage capabilities. Blockchain technologies allow miners to create only one block at a time. Transaction validation relies on the creation of those blocks. Because DAGs have nodes that are developed simultaneously, transactions can be processed faster. It's a more efficient consensus service.

Some blockchain-based distributed ledgers are suitable for only high-value transactions due to their fee structure. Alternatively, ledgers that use the DAG model are ideal for transactions of all sizes. Since DAG-based distributed ledgers aren't reliant on miners, they have lower transaction fees.

The absence of miners also means DAG-based distributed ledgers consume less energy.

A directed, acyclic future

DAG-based distributed ledgers are still in their infancy, but they offer a promising future for the ecosystem. Hedera is a leader in DAG-based technology thanks to its hashgraph consensus and gossip protocol. Hedera's DAG-based distributed technology offers low, predictable fees and lighting-fast transactions.


Related

Checkout our Gossip about Gossip Podcast