首页    期刊浏览 2024年09月12日 星期四
登录注册

文章基本信息

  • 标题:The Polling Primitive for Computer Networks
  • 本地全文:下载
  • 作者:Andrzej Czygrinow ; karonski@amu.edu.pl ; Vaidy Sunderam
  • 期刊名称:Informatica
  • 印刷版ISSN:1514-8327
  • 电子版ISSN:1854-3871
  • 出版年度:2000
  • 卷号:24
  • 期号:2
  • 出版社:The Slovene Society Informatika, Ljubljana
  • 摘要:

    We describe a distributed computing primitive termed polling that is both a means of synchronization and communication in distributed or concurrent systems. The polling operation involves the collection of messages from nodes in an interconnection network, in response to a query. We define the semantics of polling, and present algorithms for implementing the operation on complete and hypercube networks. Time and message lower bounds are presented, and are followed by an analysis of the number of operations performed at each node for every algorithm. We show that polling in a complete graph on 2^n vertices can be completed in 2n rounds using 2^n+2^{n-3} +\lceil \frac{2^{n-3}+1}{3}\rceil -1$ messages. In case of n-cube, we show that polling in 2n rounds requires $\lceil 2^n+\frac{1}{3} 2^{n-1} + \frac{1}{6} \sqrt{2^n} - \frac{4}{3} \rceil$ messages and we present an algorithm that completes polling in 2n rounds and sends $2^n +3 \cdot2^{n-4}-1$ messages.

  • 关键词:distributed computing; polling; hypercube
国家哲学社会科学文献中心版权所有