@TechReport{Dartmouth:TR97-311,
  author = {Prasad Jayanti and Sanjay Khanna},
  title = {{On the Power of Multi-Objects}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR97-311},
  year = {1997},
  month = {March},
  URL = {http://www.cs.dartmouth.edu/reports/TR97-311.pdf},
  comment = {
    Appeared in WDAG 1997, Lecture Notes in Computer Science #1320.
  },
  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.  
  }
}