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和区块链的合并是分布式账本可伸缩性的一个巨大飞跃。

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

本文转自区块网

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20181217A0ZZRM00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券