Introduction to Directed Acyclic Graphs (DAGs)
In the realm of decentralized technology, directed acyclic graphs (DAGs) are gaining attention as a superior alternative to traditional blockchains. However, DAGs are not a new concept; they have been used for thousands of years, often unknowingly. DAGs offer higher throughput by combining concepts from blockchains, proof of work and stake, and the longest chain rule with their unique structure.
The Ancient Origins of DAGs
The history of DAGs dates back long before Satoshi Nakamoto’s Bitcoin whitepaper, Leonhard Euler’s paper on the ‘Seven Bridges of Königsberg’, and even the construction of the Egyptian pyramids. The first use of a DAG is undated, but its utility stretches back to the dawn of human existence.
Understanding DAGs
In a previous article, we introduced the concept of DAGs. Simply put, a DAG is a collection of nodes representing “things,” connected by directed edges that indicate links with other “things,” ensuring no loops exist in the graph. For instance, imagine a city with only one-way streets where a person could never return to any previously visited position. This definition is rooted in Graph Theory, but DAGs have been used informally for thousands of years.
The Seven Bridges of Königsberg
Leonhard Euler’s 1736 publication ‘Seven Bridges of Königsberg’ is considered the first paper on Graph Theory. The problem involves finding a route to cross each of the seven bridges in Königsberg (now Kaliningrad, Russia) once and only once. Euler’s work simplified the city map to a graph and introduced a formula relating the number of edges, vertices, and faces.
Graph Theory and DAGs
Graph Theory has evolved into the study of relationships between objects depicted by mathematical structures. There are various types of graphs, each with specific definitions, and DAGs are one of them. Although formally defined in 1736, the ‘Seven Bridges’ problem and its mental and physical representations existed long before Euler. Similarly, DAGs were used long before their formal definition.
Ancient Use Cases of DAGs
One ancient use case of DAGs is creating family trees. Interestingly, most family trees in Graph Theory would not be considered trees due to mating between distant relatives, resulting in a common ancestor on both paternal and maternal sides. Thus, a family tree can be considered a DAG, with each node representing a person and each parent-offspring relationship depicted as an arrow pointing to the offspring. This forms a directed, acyclic graph.
Depictions of family trees as DAGs have been recorded in Ancient Rome by Pliny the Elder, who described graphs decorating Roman patrician houses. Prior to this, DAGs were often described verbally when recounting family histories.
DAGs in Task Scheduling
Another historical use case for DAGs is task scheduling. Both animals and humans instinctively use DAGs to determine the order of tasks. For example, in cooking dinner:
- Task 1: Decide which animal to hunt.
- Task 2: Hunt the animal.
- Task 3 (concurrent): Collect firewood.
- Task 4: Start the fire.
- Task 5: Cook the animal (requires tasks 2 and 4 to be completed).
- Task 6: Eat the dinner (requires task 5 to be completed).
Similar, more complex DAGs would have been used for large tasks such as building the pyramids, designing Rome, or planning a war strategy.
Modern Applications of DAGs
In modern times, DAGs have numerous applications in computer science, including data processing networks, version history management, and data compression algorithms. DAGs are not a new revelation but an age-old problem-solving mechanism. Combining DAGs with blockchains marks a significant advancement for distributed ledger scalability.
https://medium.com/fantomfoundation/history-and-use-cases-of-dags-25f05663d40d
Ecosystem
Research
News Network
About