History and Use Cases of DAGs
In terms of decentralized technology, directed acyclic graphs (DAGs) are the new kid on the block. However, DAGs have been used for thousands of years and perhaps even used unknowingly. DAGs are superior to blockchains in a sense that it allows higher throughput, by combining the concepts of blockchains, proof of work and stake, and the longest chain rule with directed acyclic graphs.
But the history of DAGs extend back to long before Satoshi first started writing the Bitcoin whitepaper, before Leonhard Euler published his paper on the ‘Seven Bridges of Königsberg’, and even before the Ancient Egyptians laid the first stone of the pyramids. The first use of a DAG is undated, but the concept is so useful, it extends back to the dawn of human existence.
In an earlier article we published, we introduced the concept of DAGs. In simple, a DAG is a collection of nodes which are representations of a “thing”, connected by directed edges that signify links with other “things”, in a way that there are no loops in the graph. For example, a city with only one way streets that if a person were to travel along any street, they could never return to any position they were at previously. It is a definition set out in Graph Theory, but DAGs have been used, without a formal definition for thousands of years before Graph Theory was formalised.
As mentioned before, the publication ‘Seven Bridges of Königsberg’ by Leonhard Euler in 1736 is regarded as the first paper to cover Graph Theory. The seven bridges of Königsberg is a notable problem in the history of mathematics. The challenge is to find a route to cross each of the seven bridges in Königsberg (now Kaliningrad, Russia) once and only once. After simplifying the map of the city to a graph, Euler introduced his formula relating the number of edges, vertices and faces.
From here, Graph Theory has developed into a study of relationships between objects, depicted by mathematical structures. There are many different types of graphs, all with specific definitions, and a DAG is one of them. Now, although graphs were not formally defined until 1736, the ‘Seven Bridges’ problem existed for hundreds of years before and, people had been creating mental and physical representations of the problem. Although there was no formal definition, these representations were graphs. Just as graphs were not defined, yet they were used, DAGs were also not defined, yet they were used!
An ancient use case of DAGs is creating a family tree. Interestingly, the definition of a tree in Graph Theory did not include most family trees. This is because in most family trees stretching back far enough, at some point distant relatives have mated, allowing a common ancestor on both the paternal and maternal sides of the family. This means, a family tree can be considered a DAG–where each node is a person, and each parent-offspring relationship is drawn as an arrow pointing towards the offspring. This forms a graph as shown below, which is directed (the arrows) and acyclic (no person can be a parent of themselves).
Depictions of family trees as DAGs have been recorded in Ancient Rome, by Pliny the Elder who described the graphs decorating the walls of Roman patrician houses. Prior to this, DAGs may not have been recorded, but often described when explaining family histories.
Another historic use case for DAGs is task scheduling where animals and humans innately use DAGs to work out the order of tasks to complete. When completing a job that requires multiple tasks, such as cooking dinner, we make a mental list of the order of tasks. Some tasks cannot begin until others are complete and other tasks can begin at any time — this in itself is a DAG.
In the above DAG, T1 may be to decide which animal to hunt for dinner, task 2 is to hunt the animal, and task 3 which can be done concurrently is to collect firewood. Task 4 is to start the fire. Task 5, to cook the animal, requires both the fire to be burning and the animal to be hunted, and task 6 is to eat the dinner, which needed the animal to be cooked first.
Similar (but more complex) DAGs would have been used for any large task, such as building the pyramids, designing Rome, planning an attack during a war, etc.
Other use cases for DAGs are more modern, with multiple uses related to computer science. Data processing networks, version history and some data compression algorithms all utilize DAGs. But the important thing to note is DAGs aren’t a new revelation, but an age old problem solving mechanism. The merge of DAGs and blockchains is a huge leap forward for distributed ledger scalability.
