Distributed Algorithms for Synchronizing Interprocess Communication Within Real Time,

Abstract

This paper considers a fixed (possibly infinite) set, pi, 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 at any time a pair of processes are mutually willing to communicate, they establish communication within a constant time interval, with high likelihood (for the worst case behavior of the system). Our communication model and synchronization algorithms are quite robust and can be applied to solve a large class of resource synchronization problems, as well as implement Dijkstra's CSP in real time. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1980
Accession Number
ADA094650

Entities

People

  • John Reif
  • Paul Spirakis

Organizations

  • Harvard University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Communication Systems
  • Computations
  • Computer Science
  • Distribution Functions
  • Efficiency
  • Intervals
  • Language
  • Message Systems
  • Military Research
  • New York
  • Packet Switching
  • Probability
  • Random Variables
  • Time Intervals

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Radio communications and signal processing.
  • Statistical inference.