Periodic Updates in Processor Networks

Other Titles


In implementing parallel scientific applications, the crux is often efficiency in communication. So, it becomes important to abstract out and study frequently occurring patterns of communication. We describe one such abstraction, periodic update, which arises in such diverse areas as computational molecular dynamics, distributed systems and n-body simulations. Consider a synchronous network of processors. Every processor needs to know the status of every other processor. The status keeps changing and it is more important to know the correct status of nearer processors. The work done in maintenance of status information should be as little as possible. The periodic update problem is that of sending (and receiving) periodic status updates from every processor to every other processor in the network in order to maintain status information. The time interval between successive updates from one processor to another is given by some increasing function (the periodicity function) of the distance between them. Given a network and a periodicity function, we wish to find efficient protocols for the periodic update problem which have minimum delay (time elapsed between the sending of an update and its receipt) and minimum peak bandwidth (maximum number of updates sent across any edge in one time-step). We present a general design paradigm and construct periodic update protocols for the one and two dimensional mesh networks for both polynomial and exponential periodicity functions. Given a periodicity function, we demonstrate a trade-off between delay and peak bandwidth. Then, using two general techniques, we transform minimum delay protocols into families of highly efficient protocols with performances spanning the entire spectrum from minimum delay to minimum peak bandwidth.

Journal / Series

Volume & Issue



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record