Distributed FIFO Allocation of Identical Resources Using Small Shared Space.

Abstract

This document presents a simple and efficient algorithm 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 the authors show the algorithm is optimal (to within a constant factor) with respect to shared space complexity. Additional keywords: fault tolerant computing; and computations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1985
Accession Number
ADA159151

Entities

People

  • A. Borodin
  • J. E. Burns
  • M. J. Fischer
  • N. A. Lynch

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Connecticut
  • Construction
  • Contracts
  • Environment
  • Fault Tolerance
  • Fault Tolerant Computing
  • Information Processing
  • Massachusetts
  • Mathematics
  • Military Research
  • Universities

Fields of Study

  • Computer science
  • Engineering

Readers

  • Computer Networking
  • Operations Research

Technology Areas

  • Space