.png){kind=icon}
返回
Threshold-Driven Streaming Graph: Expansion and Rumor Spreading
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.6.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
[11]中介绍了一种名为raes的随机分布式算法，用于从稠密n顶点扩展图G=(V, E)中提取有界度扩展器。该算法依赖于一个简单的阈值基过程。[11]中的一个关键假设是输入图G是静态的——即其顶点集V和边集E在整个过程中保持不变——而对raes在动态模型中的分析则留作一个主要开放问题。在本工作中，我们研究了由流节点更替过程（也称为滑动窗口模型）诱导的动态图模型下raes的行为，其中在每个离散轮次中，一个新节点加入图而最老的节点离开。此过程产生一个有界度动态图G={G(t)=(V-t, E-t): t是自然数的一个元素}，它捕获了对等网络的本质特征——具体而言，节点更替和每个节点可管理的连接数阈值。我们证明动态图序列中的每个快照Gt以高概率具有良好的扩展性质。此外，我们利用这一性质建立了著名的push和pull谣言传播协议在动态图G上的完成时间的对数上界。
Keyword:
Distributed Algorithms
Randomized Algorithms
Dynamic Random Graphs
Graph Expansion
Rumor Spreading
期刊
机构
引用论文
暂无论文信息