A-A+

偏序/DAG的一个例子

2020年04月11日 分布式 评论 2 条 阅读 71 次

 

序问题可以说是分布式系统中天字第一号问题,因为它来自分布式系统最基础的那个系统模型假设 - 异步网络,而且影响了分布式系统算法设计等等很多方面。分布式系统的序问题阐述起来非常庞大,这里只是简单描述下跟偏序/DAG的一个例子 - 区块链公链的DAG。

 

前面已经写过一点关于偏序的东西,读者可以参见Anna KVS中的Lattice是什么?里面介绍的一些内容。

 

首先从比特币网络开始,比特币网络作为一个分布式账本,每个人都记录了所有的交易历史,分布式账本能正常工作的一个前提是每个人的账本内容都是一样的。

比特币网络使用的是POW这种基于博弈的共识算法,确保在链的尾部只有一个节点能够追加一个/批新的交易,最终大家都认可这个唯一的链。

 

某些公链做了一个优化,将上述单链改成了DAG。

改了有什么好处

可以提高tps。

为什么可以改呢

因为很多人产生的各自的交易实际上并没有任何冲突,这些交易的顺序实际上可以从单链的全序(total order)放松成偏序(partial order)。

 

 

ps. 刚听到这个思路的时候,第一反应这个结构应该叫 “胖链表” ,英文名我都给它起好了 - FatChain。

 

 

2 条留言  访客:1 条  博主:1 条

  1. alanda

    是conflux ?

    • LoopJump

      貌似有若干方案都是,我第一次听到的确实是conflux...

给我留言