【毕设】F1算法的一个拓展

发表于 分类于

考虑【论文评述】Algorithms for Distributed Functional Monitoring | Home of Mr. 5中的通用算法，对于，我们有通讯复杂度为，这里，如果我们认为，那么也就是。这个假设可以这么理解，由于我们的计数是离散的，那么“最精细”的误差也只能是，也即，也即。在接下来的讨论中，我们都默认。

考虑下面这个模型，只有A、B两个站点，那么原paper中的算法其实可以等价为下面这个算法：

  1. 初始化，将通知A、B，初始化阶段编号，，；

  2. 进入阶段，接收数据，直到A（或B）在阶段（或）到阶段收到的数据量超过，通知中心，并令（或）；

  3. 若，停止；否则，令，将分发给A、B，，回到第2步；

通讯复杂度显然为。

现在我们假设，A向中心上传信号的时间开销是原来的倍。对于这种通讯时长不均一的模型，上述通用算法会产生一些比较差的结果。

考虑这样的输入，所有数据都是涌向A的，B从始至终没有收到任何数据，那么上述算法会导致的通讯复杂度。

我们提出一个新的算法，把复杂度降低到：

  1. 初始化，将通知A、B，初始化阶段编号，，；

  2. 进入阶段，接收数据，直到A（或B）在阶段（）到阶段收到的数据量超过（），通知中心，并令（），（）；

  3. 若或，停止；否则，令，将和分别发送给A、B，，回到第2步；

，其中为在上的解。

这个的复杂度是怎么来的呢？

A至多通讯次，B至多通讯次，

因此复杂度至多为。

注意到，

取使得，即

则进一步有

，

因此我们现在就是要知道，当增长时，是怎样增长的。

我们知道，当时，。

令，则有

又由于，方程化为

，取对数

令，有

，解得

，其中为乘积对数函数。

则

，又因为，且，则

，则

，则

因此算法的通信复杂度为。

（可以把代入回原式检验，然后在处展开，展开结果可以让引擎计算）

不过，如果模型推广到个节点，且最长通讯时长仍为的话，那么算法也会退化到。但我们可以相信，在大部分情况下（特别是随机情况下），这个算法是更好的。因此我们可以构造实验来验证（目前也只能靠实验验证，因为渐进复杂度是一样的）。当然，在这之前，我们先明确一下如何将这个算法推广到一般情况，即个节点的上传速度分别是。则算法每次分配本地阈值就按照（加只是为了防止）的比例来分配。

随机情况试验：

令，在的整数上随机生成。

输入个数据，输入站点在上随机生成。

特殊情况试验：

  1. 数据仅向值最大的输入

  2. 数据仅向值最小的输入

  3. 数据仅向值中等的输入

以上实验对原始算法和新算法都同时运行，保存实验数据以及相关代码。