Browse Prior Art Database

A Wait-free Concurrent Timestamp System

IP.com Disclosure Number: IPCOM000122341D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 36K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR

Abstract

Described is a method for distributively managing a concurrent timestamp system. Processors communicate through atomic registers and are completely asynchronous. The method enables processors to timestamp their values without waiting for the completion of any operation by any other processor.

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

A Wait-free Concurrent Timestamp System

      Described is a method for distributively managing a concurrent
timestamp system.  Processors communicate through atomic registers
and are completely asynchronous.  The method enables processors to
timestamp their values without waiting for the completion of any
operation by any other processor.

      The set of timestamp values is the set of nodes of some
explicit recursive graph.  A processor that wants to get a new
timestamp needs collect the timestamps of the other processors,
analyze the graph, and choose its new timestamp, which it writes to
its registers.  No matter at what stage other processors are and how
many try to choose timestamps at once, each processor completes its
operation independently.

      A processor which scans to find the latest timestamp, or the
order of timestamps, does not need to write or notify others that it
intends to do so.  It only collects the timestamps (several times).
An analysis of the values it has received enables it to determine the
order.

      Comparing a pair of timestamps requires only scanning of the
binary representation of the two timestamps from left to right.

      Disclosed anonymously.