Skip to main content

Real-Time Synchronization of Interprocess Communications

Publication ,  Journal Article
Reif, JH; Spirakis, PG
Published in: ACM Transactions on Programming Languages and Systems (TOPLAS)
April 1, 1984

This paper considers a fixed (possibly infinite) set of distributed asynchronous processes, which at various times are willing to communicate with each other. Each process has various ports, each of which is used for communication with a distinct neighbor process. Each process can have at most one port open at any time, and its other ports must be closed. Two processes handshake over a time interval A if their respective ports are open for mutual communication during this interval. Note that the handshake relation is a matching. Successful communication requires a handshake of at least one step of each process; during the one-step overlap a message can be transmitted between processes. The problem is to synchronize processes (via a distributed scheduler) so that they can successfully handshake at their will, given that the means of synchronization is some low-level construct that does not guarantee the handshake property if used in an unsophisticated way. Probabilistic distributed algorithms for synchronizing processes so that they can handshake at will are described. A process is considered to be tame over a time interval A if its speed varies within certain arbitrarily fixed nonzero bounds. Our synchronization algorithms are shown to have real-time response: If a pair of processers are mutually willing to communicate within a time interval A of length at least a given constant and the pair are tame on A, then they establish communication within A with high likelihood (for the worst case behavior of the system), and the expected time for establishment of communication is also constant. Our model and algorithms are applied to solve a large class of real-time resource allocation problems, as well as real-time implementation of the synchronization primitives of Hoare's multiprocessing language CSP. © 1984, ACM. All rights reserved.

Duke Scholars

Published In

ACM Transactions on Programming Languages and Systems (TOPLAS)

DOI

EISSN

1558-4593

ISSN

0164-0925

Publication Date

April 1, 1984

Volume

6

Issue

2

Start / End Page

215 / 238

Related Subject Headings

  • Software Engineering
  • 4612 Software engineering
  • 4606 Distributed computing and systems software
  • 0806 Information Systems
  • 0803 Computer Software
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Spirakis, P. G. (1984). Real-Time Synchronization of Interprocess Communications. ACM Transactions on Programming Languages and Systems (TOPLAS), 6(2), 215–238. https://doi.org/10.1145/2993.357244
Reif, J. H., and P. G. Spirakis. “Real-Time Synchronization of Interprocess Communications.” ACM Transactions on Programming Languages and Systems (TOPLAS) 6, no. 2 (April 1, 1984): 215–38. https://doi.org/10.1145/2993.357244.
Reif JH, Spirakis PG. Real-Time Synchronization of Interprocess Communications. ACM Transactions on Programming Languages and Systems (TOPLAS). 1984 Apr 1;6(2):215–38.
Reif, J. H., and P. G. Spirakis. “Real-Time Synchronization of Interprocess Communications.” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 6, no. 2, Apr. 1984, pp. 215–38. Scopus, doi:10.1145/2993.357244.
Reif JH, Spirakis PG. Real-Time Synchronization of Interprocess Communications. ACM Transactions on Programming Languages and Systems (TOPLAS). 1984 Apr 1;6(2):215–238.

Published In

ACM Transactions on Programming Languages and Systems (TOPLAS)

DOI

EISSN

1558-4593

ISSN

0164-0925

Publication Date

April 1, 1984

Volume

6

Issue

2

Start / End Page

215 / 238

Related Subject Headings

  • Software Engineering
  • 4612 Software engineering
  • 4606 Distributed computing and systems software
  • 0806 Information Systems
  • 0803 Computer Software