• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE International Conference on Network Protocols >Overlay Topology as Random-Walk Cache
【24h】

Overlay Topology as Random-Walk Cache

机译：覆盖拓扑作为随机步行缓存

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A probabilistic quorum system (PQS) allows distributed services to be replicated on only a subset (quorum) of servers. The replicas can be kept consistent with high levels of assurance as long as any two quorums intersect with very high probability. PQS thus provides a means to trade off levels of consistency against the scalability and efficiency of a quorum system. When quorums are constructed by choosing members of the subset uniformly at random, the non-intersection probability can be easily computed. On a distributed system with n servers, uniform sampling is often conducted using random walk of length O(log n). To collect multiple uniform samples naively would require as many random walks. A number of works have relied on analytical results based on the Chernoff bound to reduce the number of random walks needed to collect multiple samples. Controlled flooding is another efficient method to collect multiple samples. In this paper we evaluate both methods analytically and found that quorums formed using either method cannot satisfy the non-intersection probability bound associated with quorum formed by uniform sampling. Our contributions are: (1) to show that overlay topology can be constructed to cache multiple random walks, (2) to show that repeated use of this cache to obtain multiple uniform samples leads to degradation of sample uniformity over time, and (3) to propose and evaluate graph re-wiring as a simple method to keep the cache fresh, to take advantage of overhead reduction of random walk caching while alleviating the degradation in sample uniformity.
机译：概率Quorum系统（PQS）允许仅在服务器的子集（仲裁）上复制分布式服务。只要任何两个概率相交，复制品可以保持符合高水平的保证。因此，PQS提供了衡量符合仲裁系统的可扩展性和效率的一致性的方法。当通过以随机均匀地选择子集的构件来构造法定值时，可以容易地计算非交叉概率。在具有N服务器的分布式系统上，通常使用长度O（log n）随机步行进行均匀采样。收集多个统一样本，天然需要多个随机散步。基于Chernoff的分析结果依赖于突破的分析结果依赖于减少收集多个样本所需的随机行走数量。受控洪水是收集多个样品的另一种有效的方法。在本文中，我们在分析上评估了这两种方法，发现使用任一方法形成的法定记录不能满足与通过均匀采样形成的法定核相关联的非交叉点概率结合。我们的贡献是：（1）显示叠加拓扑可以构建为缓存多个随机播放，（2）显示重复使用此高速缓存以获得多个均匀样本导致样本均匀性随时间的均匀性降低，以及（3）为了提出和评估图形重新布线作为保持缓存新鲜的简单方法，利用随机步道缓存的开销减少，同时减轻了样本均匀性的降级。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号