Distributed FIFO Allocation of Identical Resources Using Small Shared Space.

Abstract

A simple and efficient algorithm is presented for the FIFO allocation of K identical resources among asynchronous processes which communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against processes failure through unannounced stopping, making it attractive also for use in an environment of processes of widely differing speeds. In addition to its practical advantages we show the algorithm is optimal (to within a constant factor) with respect to shared space complexity. Keywords: Resource allocation, Shared-memory algorithm, Queue asynchronous system, Robustness and Critical section.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1985
Accession Number
ADA163988

Entities

People

  • Allan Borodin
  • James E. Burns
  • Michael J. Fischer
  • Nancy Lynch

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Asynchronous Systems
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Continents
  • Environment
  • Information Processing
  • Language
  • Massachusetts
  • Military Research
  • Theoretical Computer Science
  • Transitions
  • Universities

Fields of Study

  • Engineering

Readers

  • Operations Research
  • Parallel and Distributed Computing.

Technology Areas

  • Space