In this paper we consider a variant of population protocols in which agents are allowed to be connected by edges, known as the constructors model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The contributions of this paper are manifold. -- We propose and analyse a novel type of phase clocks allowing to count parallel time $\Theta(n\log n)$ in the constructors model. This new type of clocks can be also implemented in the standard population protocol model assuming a unique leader is available. -- The new clock enables a nearly optimal $O(n\log n)$ parallel time spanning line construction which improves dramatically on the best previously known $O(n^2)$ parallel time solution. -- We define a probabilistic version of bubble-sort in which random comparisons are allowed only between adjacent numbers in the sequence being sorted. We show that rather surprisingly this probabilistic bubble-sort requires $O(n^2)$ comparisons in expectation, i.e., on the same level as its deterministic counterpart. -- We propose the first self-replication protocol allowing to reproduce a {\em strand} (line-segment carrying information) of length $k$ in parallel time $O(n(k+\log n)).$ This result is based on the probabilistic bubble-sort argument. This protocol permits also simultaneous replication where $l$ copies of the strand can be obtained in time $O(n(k+\log n)\log l).$ All protocols in this paper operate with high probability.
翻译:在本文中,我们考虑一个人口协议的变体, 允许代理商通过边缘连接, 称为构建者模型。 在两个代理商之间的互动中, 相关的连接边缘可以通过过渡功能形成、 维护或消除。 本文的贡献是多方面的。 -- 我们提议和分析一种新型的阶段钟, 允许在构建者模型中计算平行时间$\ Theta( n\log n) 美元。 这种新型的时钟也可以在标准的人口协议模式中实施, 假设有一个独特的领先者 。 -- 新时钟可以让一个几乎最佳的 $O( n\log n) 平行时间跨线的构建, 从而在最已知的 $O( n\ 2) 的平行时间解决方案中大大改进。 -- 我们定义了一个气泡- 状态的概率化版本, 允许在正在排序的序列中的相邻数字之间进行随机比较。 我们显示, 令人惊讶的是, 这种不稳定的气泡- 质化气旋- sort 模式需要 $ (n2) 比较, 也就是, 和它的确定性对应的 $( rominal n) ral ral ral) ral ral col- passal exal pass passil exil exil ex) 。