继上一次关于付出网络中路由问题的全面研讨之后，酷爱研讨的 Nervos 小伙伴 Shor 对通道网络中的再平衡（Rebalancing）算法又做了详细的研讨。
本文中，咱们会介绍通道网络（Channel Network，CN）中的 Rebalance 问题。首要咱们将介绍问题的定义和现有的处理算法。之后，咱们会针对这一问题，介绍必要的图论根底和建模办法。最后，咱们供给一种算法加速思路。（本文默许读者具备关于通道网络的常识。）
咱们把一个付出网络看作一个无向图，每个图中的节点代表一个 PID，每条边代表一个付出通道，其间每条边在两头节点各有一个存量。注意：咱们默许每个（双向）付出通道内部总存量守恒，即由 A，B 组成的通道中，假如 A 有余额 50，B 有余额 80，B 在向 A 付出 10 元后，A 有余额 60，B 有余额 70。
有时，由于网络拓扑结构等原因，一个付出通道的一个方向总比另一个方向「更受欢迎」，在此情况下，各个通道的有限总存量都被「堆积」到一侧，或者说「受欢迎方向」的流量就此耗尽了。因此，付出网络会频繁呈现通道流量耗尽，不得不再次「上链」翻开新通道的情况。再平衡（rebalancing）技术经过以下方式企图缓解这一问题。
例如下图中, 咱们考虑一个由四条边构成的回路，他们干流方向的 10 单位余量都已经耗尽。
其间每个箭头 
表示一个连接了 A 与 B 的无向通道，其间 A 方存量是 a，B 方存量是 b。值得注意的是，箭头方向代表了干流方向，因此咱们画成了一个有向图，不过最新基于 RbR 的付出通道都是双向的。Revive 经过一个来自全局 leader 的和谐（本文中，咱们不予考虑这个 leader 是怎么实现的），完成一个 rebalance 工作。例如，能够和谐 B 向 A 转账 5 个单位，和谐 A 向 C 转账 5 个单位，和谐 C 向 D 转账 5 个单位，和谐 D 向 B 转账 5 个单位，使得全图结构如下图所示。其本质上是找到一个「回路」，并在这个回路上让一切通道一同逆着干流方向回流、抵回一些流量。
当咱们提及 Rebalance 时，到底在企图处理哪些问题？
极大强连通重量对任何一个有向图的一切节点完成了一个 partition。
存在一个极高效的 O(N) 算法求出任一有向图的一切极大强连通重量（详细算法本文中不赘述）。
将每个极大强连通重量看作一个整体，用边连接一切有访达联系的重量并缩点后，咱们得到了一个有向无环图。
接下来，咱们介绍详细算法。
首要，咱们对原付出网络图做一个简化变幻，将每一个双向通道变换为从存量多的一方指向存量少的一方的有向边，边的容量是两头存量差的一半。例如下图中，咱们将上图变换为下图。
所以，咱们将寻找回路问题转化成了寻找有向图环路的问题。有向图的每一条边代表了一个为了让原图的对应通道更加平衡需要回流流量的一个「势能」。每一个环路能够被看作一个回流计划。在进行强连通重量缩点后，咱们只需要经过现有线性规划解每一个极大强连通重量内部的 rebalance 问题。
其处理计划便已明朗：只需要求解出这个有向图的一切极大强连通重量，并且在每一个极大强连通重量中经过常规的线性规划，求得一个最优的调度计划。由于咱们以为每个回路并不会跨两个不同的极大强连通重量，所以咱们以为这个办法求出的就是全局的最优调度计划。
这儿其实有个小问题：这真的是个等价转化吗？脚踏实地地说并不是（尽管乍看是的）。有可能会呈现最优全局调度计划中有回路横跨两个极大强连通重量的情况，由于有可能会呈现「需要为了多数人苦一苦少量人」（「需要让少量边更加不平衡来让更多边变得更平衡」）能得到更优解的可能性。不过笔者暂时以为这种误差是值得的。况且，涉及到实际落地，兴许那些少量人并不会接受这样的调度。
仔细的读者们应该发现了本文中的两个没有解释清楚的问题：
1. 到底优化了多少？
这个问题，本质上在问未来的大规模付出网络会有多少个极大强连通重量，重量越多，优化作用就越明显。本质上这个问题是未来大规模付出网络的拓扑结构是怎么样的。能够预期的是，假如绝大多数大众节点的度数只要 4 度左右，极大强连通重量的期望数量是关于网络节点数量以一种低于线性的速度增加的。
2. 上文中的（伪）等价转化牺牲了多少？
其实，这两个问题本质上都在问：未来的大规模通道网络的拓扑结构究竟是怎么样的？
笔者以为，这个问题不但笔者答复不了，恐怕也没有人能准确答复的了。这一点笔者已经在之前的文章「一份关于付出网络中路由问题的全面研讨」中给出了解释。
视野开拓
比如说，在美国这样一个经济体，贸易完全自由化的话，每获得一元的贸易“净”效益就要对50元的收入进行重新分配！重新读一遍上面的句子，你可能读得太快了。我们说的是每一美元的总效益要求我们对50元进行重新分配。这就好像是如果我们要把51元给亚当，却要从大卫那里拿来50元。 重新分配和经济效益之比那么高的一个主要原因是，现在的关税就是那么低。如果关税是40%，这个比例就是6左右。但是，就算是6，拿了大卫的去给亚当的数也是很大的。在制定其他领域的政策时，如果我们不能确定这个分配过程符合我们的公平分配原则，我们是不可能支持这么大量的重新分配的。 面临这样的情况，我们都想进行进一步的调查研究。大卫和亚当是谁，为什么要进行这个交换？大卫比亚当穷吗？大卫比亚当富吗？穷多少？富多少？这个交换对他们还有他们的家人有何影响？大卫是不是有社会安全保障网或者是其他政府补偿计划的支持？回答了这些问题，有些情况就变得容易理解了。如果大卫很有钱，很懒，或者因为某些原因不配有这50元，并且应该为造成这个损失的决定负全部责任，这个重新分配可能还可以接受。但是，如果以上说法不成立，亚当用不道德的手段促使这个重新分配发生，我们又该怎么办？ 当面临贸易引起的重大重新分配时，我们也必须提出这些问题。其中两个问题最为重要。与低收入或其他没有社会安全网保护的弱势群体的潜在损失相比，经济效益是否太小了？与贸易有关的行为是否违反了本国广为接受的社会习俗或契约，如雇用童工、违反劳工权益或者对环境造成破坏。如果对两个问题的答案都是“是”，贸易的合法性与适用性就被打上了问号。我们应该就如何解决重新分配比例过高的问题展开公共辩论，辩论的结果有可能要我们对贸易进行多一些的干预。-《全球化的悖论》
