Distributed algorithms for synchronizing interprocess communication within real time


Conference Paper

© 1981 ACM. This paper considers a fixed (possibly infinite) set Π of distributed asynchronous processes which at various times are willing to communicate with each other. We describe probabilistic algorithms for synchronizing this communication with boolean "flag" variables, each of which can be written by only one process and read by at most one other process. With very few assumptions (the speeds of processes may vary in time within fixed arbitrary bounds, and the processes may be willing to communicate with a time varying set of processes (but bounded in number), and no probability assumptions about system behavior) we show our synchronization algorithms have real time response: If a pair of processes are mutually willing to communicate within a constant time interval, they establish communication in that interval, with high likelihood (for the worst case behavior of the system). Our communication model and synchronization algorithms are quite robust. They are applied to solve a large class of real time resource synchronization problems, as well as real time implementation of the synchronization primitives of Hoare's multiprocessing language CSP.

Full Text

Duke Authors

Cited Authors

  • Reif, J; Spirakis, P

Published Date

  • May 11, 1981

Published In

Start / End Page

  • 133 - 145

International Standard Serial Number (ISSN)

  • 0737-8017

International Standard Book Number 10 (ISBN-10)

  • 0897910419

Digital Object Identifier (DOI)

  • 10.1145/800076.802467

Citation Source

  • Scopus