Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Bounded Critical Section in a Completely Asynchronous System

IP.com Disclosure Number: IPCOM000107239D
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 1 page(s) / 37K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR

Abstract

Described is a method for distributively managing a fault-tolerant multi-slotted critical section. The method produces algorithms that require only actively participating processors to communicate.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

Bounded Critical Section in a Completely Asynchronous System

      Described is a method for distributively managing a
fault-tolerant multi-slotted critical section.  The method produces
algorithms that require only actively participating processors to
communicate.

      The priority to access the critical section is determined by
the number of previous accesses and the order in which processors
have asked to access the common resources.  Each processor remembers
the number of times it has accessed the critical section.  When a
processor wants to access it again, it communicates with the other
processors to find out their state.  It maintains a database of those
processors which have higher priority.  Once its priority is high
enough, it notifies others and enters the critical section.

      Even though the communication medium is completely asynchronous
and faults may appear, the protocol is guaranteed to prevent too many
processors from entering the critical section at once.  It ensures
basic fairness conditions and is deadlock and lockout free.

      Also, another very simple protocol is described.  That protocol
requires sending of a single bit but needs the participation of all
processors, even when they are not interested in accessing the
critical section.

      Disclosed anonymously.