DAG的现代用例，和区块链的合并是分布式账本可伸缩性的一个巨大飞跃

DAG

在去中心化技术方面，有向无环图(DAG)是一个新的领域。然而，DAG已经在其他领域不知不觉的使用了数千年。在某种意义上来说，DAG优于区块链，因为它结合了区块链的工作量证明和权益证明的概念，以及具有有向无环图的最长链规则，从而允许更高的吞吐量。

但DAG的历史可以追溯到中本聪第一次写比特币白皮书之前，莱昂哈德•欧拉(Leonhard Euler)发表关于“哥尼斯堡七桥”(Seven Bridges of Konigsberg)的论文之前，甚至可以追溯到古埃及人铺设金字塔第一块石头之前。人们并不知道DAG的第一次使用的具体时间，但是这个概念非常有用，它可以追溯到人类存在的早期。

简单地说，DAG是节点的集合，这些节点表示“事物”，由表示与其他“事物”链接的有向边连接，在图中没有循环。例如，一个城市只有一条街道，如果一个人沿着任何街道旅行，他都永远不能回到以前的任何位置。它是图论中给出的一个定义，但是在图论正式形成之前的几千年里，DAG一直没有一个正式的定义。

如前所述，莱昂哈德·欧拉于1736年发表的《哥尼斯堡的七桥》被认为是第一个涉及图论的论文。哥尼斯堡七桥是数学史上一个引人注目的问题。将城市地图简化成图形后，欧拉引入了关于边、顶点和面数的公式。

图论发展成为一门研究对象之间关系的学科，并且用数学结构来描述的。有许多不同类型的图，都有特定的定义，DAG就是其中之一。虽然图论直到1736年才被正式定义，“七座桥”问题在此之前已经存在了几百年，人们一直在创造这个问题的心理和物理表征。虽然没有正式的定义，但这些表示都是图形。正如图形没有定义，但它们被使用了一样，DAG也没有定义，但它们也被使用了!

DAG的一个古老用例是创建一个家谱。有趣的是，图论中树的定义并不包括大多数的系谱树。这是因为，在大多数历史足够久远的家族中，在某些时候，远亲会进行交配，从而在家族的父系和母系双方都有一个共同的祖先。这意味着，一个家谱可以被认为是一把匕首，其中每个节点都是一个人，并且每个父子关系都被画成指向后代的箭头。这形成了一个如下图所示的图，它是有向的(箭头)和无环的(没有人可以是自己的父母)。

古罗马时期，老普林尼(Pliny the Elder)就有记载，他描绘了装饰罗马贵族住宅墙壁的图形。在此之前，DAG可能没有被记录下来，但在解释家族史时经常被描述出来。

DAG的另一个历史用例是任务调度，动物和人类都在使用DAG来计算任务完成的顺序。当需要完成多项任务的工作时，比如做饭，我们会在脑海中列出任务的顺序。有些任务在其他任务完成之前不能开始，而其他任务可以在任何时候开始——这本身就是一个DAG。

在上面的DAG中，T1可能是决定猎食哪种动物，T 2是猎食动物，T3是收集柴火，可以同时进行。T4是生火。T5是烹饪动物，这需要生火和猎食动物，而T6是吃晚餐，这需要动物首先被烹饪。

类似的(但更为复杂的)DAG可以用于任何大型任务，如建造金字塔、策划战争期间的袭击等等。

DAG的其他用例更加现代，具有与计算机科学相关的多种用途。数据处理网络和一些数据压缩算法都使用DAG。但是值得注意的是，DAG并不是一个新的发现，而是一个古老的问题解决机制。DAG和区块链的合并是分布式账本可伸缩性的一个巨大飞跃。

*文章仅代表作者个人观点

本文转自区块网