Fast gossiping on mesh-bus computers

Satoshi Fujita, Masafumi Yamashita

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


A mesh-bus computer is a parallel computer in which nodes (i.e., processors) are arranged on a two-dimensional array, and nodes on each row and nodes on each column, respectively, are connected by a shared bus. The nodes communicate with each other by exchanging packets through shared buses in CREW manner. Suppose that each node initially contains a piece of information called a token. A gossiping problem is the routing problem of exchanging tokens among all nodes in the computer, which has been studied extensively as a basic communication scheme for sharing information among nodes in a parallel computer. In this paper, we propose three gossiping algorithms for mesh-bus computers assuming that each packet can carry at most ℓ tokens in a step, where ℓ is a function of the number of all nodes. It is shown that by selecting the fastest algorithm among them, for each given function ℓ, a lower bound on the gossiping time can be attained asymptotically.

Original languageEnglish
Pages (from-to)1326-1330
Number of pages5
JournalIEEE Transactions on Computers
Issue number11
Publication statusPublished - Dec 1 1996

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Fast gossiping on mesh-bus computers'. Together they form a unique fingerprint.

Cite this