1. 首页
  2. 基本原理

ByteBall中DAG的几个性质

DAG是有向无环图,它由结点和边组成。在ByteBall中有一条特殊的路径,称为主链,它用来实现DAG中结点的全局定序。一般来讲,ByteBall的DAG可以表示为如下形式,其中中间粗箭头连接的为主链。

dag

对于DAG中的一个结点,ByteBall定义了如下几个属性:

  1. level:表示结点所处的层级,通过递归方式进行计算,子结点的level等于父结点中最大的level加1,记作符号$L$。
  2. main_chain_index:表示结点与主链关联的序号,称为主链序号,记作符号$MCI$。如果结点位于主链上,则$MCI$为主链上前一结点的$MCI$加1;如果结点不在主链上,则其$MCI$为主链上最早包含该结点的主链结点的$MCI$(即离开主链的最小位置);若结点不在主链上,且主链上任何结点都不包含该结点,则$MCI$为空。
  3. latest_included_mc_index:表示该结点包含的主链节点的最大$MCI$(即从该结点回到主链的最大位置),记作符号$LIMCI$。创世结点的$LIMCI$为空。
  4. witnessed_level:表示结点的见证级别,从当前结点的最优父结点沿主链开始回溯,当路径上出现多于7个不同见证人发出的结点时停止回溯,witnessed_level等于回溯停止处的结点的级别level,记作符号$WL$。

给定结点$i$和结点$j$,它们对应的属性分别记作:

  • $L_i$, $MCI_i$, $LIMCI_i$, $WL_i$
  • $L_j$, $MCI_j$, $LIMCI_j$, $WL_j$

如果存在一条从结点$j$到达结点$i$的路径,则称结点$i$被结点$j$包含或者结点$j$包含结点$i$。那么,我们可以推导得出以下一系列的性质

性质1: 子结点的level一定大于父结点的level

显然,根据结点level的定义可以很容易得到上面的性质。进一步地,我们可以得到:

性质2: 如果结点$i$被结点$j$包含,则一定有$L_j > L_i$;如果$L_i \ge L_j$,则结点$i$一定不被结点$j$包含。

通过反证法可以很容易得出以下性质:

性质3: 当$MCI$不为空时,子结点的$MCI$一定大于等于父结点的$MCI$。

性质4: 如果结点$i$被结点$j$包含,则一定有$MCI_j \ge MCI_i$;如果$MCI_i > MCI_j$,则结点$i$一定不被结点$j$包含。

性质5: 子结点的$LIMCI$一定大于等于父结点的$LIMCI$。

性质6: 如果结点$i$被结点$j$包含,则一定有$LIMCI_j \ge LIMCI_i$;如果$LIMCI_i > LIMCI_j$,则结点$i$一定不被结点$j$包含。

性质7: 当子结点与父结点的见证人列表相同时,子结点的$WL$一定大于等于父结点的$WL$。

性质8: 如果结点 $i$ 被结点$j$包含,则一定有$WL_j \ge WL_i$;如果$WL_i > WL_j$,则结点$i$一定不被结点$j$包含。

此外,在结点的$MCI$和$LIMCI$这两个属性之间也具有如下几条性质:

性质9: 当一个结点的$MCI$不为空时,则一定满足MCI > LIMCI

性质10: 如果结点$i$被结点$j$包含,则一定有$MCI_j \ge MCI_i > LIMCI_i$以及$MCI_j > LIMCI_j \ge LIMCI_i$。

性质11: 如果$LIMCI_i \ge MCI_j$,且$MCI_j$不为空,则结点$i$一定不被结点$j$包含;如果$LIMCI_j \ge MCI_i$,且$MCI_i$不为空,则结点$i$一定被结点$j$包含。

性质12: 如果结点$i$被结点$j$包含,且结点$j$位于主链上,则$LIMCI_j \ge MCI_i$。

这些性质在快速判断两个结点之间的关联关系时具有很大的作用,可以提高计算速度。具体的一些代码示例可以参考 graph.js

版权所有。发布者:Alan During,转载请注明出处:https://bbfans.org/2018/10/22/byteball-dag-properties/

发表评论

登录后才能评论

联系我们

加入ByteBall技术群请添加

QR code