BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR97-311
ENTRY:: January 05, 1998
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: On the Power of Multi-Objects
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Jayanti, Prasad
AUTHOR:: Khanna, Sanjay 
DATE:: March 1997
ABSTRACT:: 
In the standard ``single-object'' model of shared-memory computing, it
is assumed that a process accesses at most one shared object in each
of its steps.  In this paper, we consider a more powerful
variant---the ``multi-object'' model---in which each process may
access *any* finite number of shared objects atomically in each of its
steps.  We present results that relate the synchronization power of a
type in the multi-object model to its synchronization power in the
single-object model.
 Although the types fetch&add and swap have the same synchronization
power in the single-object model, Afek, Merritt, and Taubenfeld showed
that their synchronization powers differ in the multi-object model.
We prove that this divergence phenomenon is exhibited {\em only\/} by
types at levels 1 and 2; all higher level types have the same
unbounded synchronization power in the multi-object model stated
above.
 This paper identifies all possible relationships between a type's
synchronization power in the single-object model and its
synchronization power in the multi-object model.  
NOTE:: Appeared in WDAG 1997, Lecture Notes in Computer Science #1320.
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR97-311.pdf
END::