For the most recent entries see the Petri Nets Newsletter.

On the Power of Multi-objects.

Jayanti, Prasad; Khanna, Sanjay

In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 320-331. Springer, September 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. A (more powerful) variant is the multi-object model in which each process may access an arbitrary finite number of shared objects simultaneously in each atomic step. In this paper, 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. Afek, Merritt, and Taubenfeld considered the case where one could access up to a given number of objects simultaneously as well as the case where one could access any finite number of objects simultaneoulsy in a single atomic step. We consider only the case where one may access an arbitrary finite number of objects simultaneously. 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 only by types at level 1 and 2; all higher level types have the same unbounded synchronization power in the multi-object model. This paper identifies all possible relationships between a types's synchronization power in the single-object model and its synchronization power in the multi-object model, where as many objects of one type as required may be accessed in a single atomic step.

Keywords: shared objects; multi-objects; waitfree; implementation; object hierarchy.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography