From: kk@cpsc.ucalgary.ca (Ken Kittlitz)
Newsgroups: fj.mail-lists.parallel
Subject: SUMMARY: Evaluating Concurrency Control...
Date: 6 Apr 92 15:23:45 GMT
Article-I.D.: nttlab.283117
Distribution: fj

About a week ago I posted the following request:


I've received a number of responses -- thanks to all who replied.  Below
is a summary of these.

			Mechanism Evaluation
			--------------------

A. Lester Buck  (buck@siswat.hou.tx.us)...

...made the excellent suggestion of doing an Science Citation Index search on
Bloom's paper, which I did. Unfortunately, none of the papers which
referenced Bloom's work appear to have followed up on it -- most seem to be
discussions of specific control mechanisms, not evaluation criteria.
However, courtesy of the ACM Guide to Computing Literature, I found the
following reference:

Barz, H.  "The Power of Synchronization Mechanisms."  SIAM Journal on
Computing (13) 4 (Nov., 1984), starts on pp. 726.

	-Haven't had a chance to look at this yet, but it sounds
	 promising.


>From Ted Johnson <ted@squall.cis.ufl.edu>:

Ken,
I've done some performance evaluation of concurrency control mechanisms:
1) reader/writer queues: see the 1990 SIGMETRICS, look for
my paper.  it contains references to previous work.
The paper was subsequently extended by Wright and Courtouris
in the 1991 SIGMETRICS.  My analysis is much simpler, though less
general and less exact.
2) spin locks: in Supercomputing '91, I have a paper with Ray Glenn et al.
(look for Glenn's paper).  This paper also refers to some
previous work, most notably that of Anderson and Lazowska.
3) single-writer/many reader queues: I have some performance
results for a reader/writer queue in which at most 1 writer is
ever in the queue at a time.  If you think that my SIGMETRICS
paper is interesting, I'll send you a copy of my thesis.

These are all performance analysis, BTW, and don't address other
issues.
	Ted

---------------------------------------------------------------------------

		Other Concurrency Control Mechanisms
		------------------------------------

From: suhler%pollux.usc.edu@usc.edu (Paul A. Suhler):

One particular mechanism that you may want to look at is k-bounding
of loops that came out of Arvind's Computation Structures Group
at MIT.  I don't know a particular reference, but if you find a
paper on the Id language or on the Tagged-Token Dataflow Architecture,
you'll probably find references to it and to other techniques.


From: Oscar Nierstrasz <oscar@cui.unige.ch>:

There has been a lot of work recently in the concurrent OOP
community, looking at how to combine concurrency with OOP features.
The Kafura & Lee paper is the first of a number by various authors
on combining synchronization features and inheritance.

Below are some references that might be of interest.

Oscar

%L Lisk86b
%K concurrency popl86
%A B. Liskov
%A M. Herlihy
%A L. Gilbert
%T Limitations of Synchronous Communication with Static Process
Structure in Languages for Distributed Computing
%B Proceedings POPL '86
%C St. Petersburg Beach, Florida
%D Jan 13-15, 1986

%L Kafu89a
%K olit obcl concurrency act++ inheritance ecoop89 binder(oop) obib(obcp)
%A D.G. Kafura
%A K.H. Lee
%T Inheritance in Actor Based Concurrent Object-Oriented Languages
%B Proceedings ECOOP '89
%C Nottingham
%I Cambridge University Press
%D July 10-14, 1989
%P 131-145

%L Kafu91a
%K olit obcl concurrency act++ obcs90
%A D.G. Kafura
%A G. Lavender
%T Recent Progress in Combining Actor-Based
Concurrency with Object-Oriented Programming
%J ACM OOPS Messenger, Proceedings OOPSLA/ECOOP 90 workshop
on Object-Based Concurrent Systems
%V 2
%N 2
%D April 1991
%P 55-58

%L Neus91a
%K olit ecoop91
%A C. Neusius
%T Synchronizing Actions
%B Proceedings ECOOP '91
%E P. America
%S LNCS 512
%I Springer-Verlag
%C Geneva, Switzerland
%D July 15-19, 1991
%P 118-132

%L Papa92b
%K olit obc chloe
%A M. Papathomas
%T Language Design Rationale and Semantic Framework for Concurrent
Object-Oriented Programming
%R Ph.D. thesis
%I Dept. of Computer Science, University of Geneva
%D 1992
%O forthcoming

-----------------------------------------------------------------------

While we're at it, here are a few refs I've found interesting:

Livesey, M. Distributed Varimistic Concurrency Control in a Persistent Object
Store. {\em Implementing Persistent Object Bases: Principles and Practice
(Fourth	International Workshop on Persistent Object Systems\/} (Palo Alto:
Morgan Kaufmann Publishers, Inc., 1991), 293-304.

	-Modification of Jefferson's time warp synchronization scheme
	 to make it more suitable for transaction-based concurrency
	 control.

Parrington, G.D., \& Shrivastava, S.K. Implementing Concurrency Control in
Reliable Distributed Object-Oriented Systems. {\em Proc. ECOOP '88\/}
(Oslo, Norway: Aug. 15-17, 1988). Springer-Verlag lncs 322, pp.233-249.

	-Shows how concurrency control using locks can be implemented
	 in a type-specific manner in C++.  Code given is part of
	 the Arjuna system.

Tomlinson, C. \& Singh, V. Inheritance and Synchronization with
Enabled-Sets. {\em Proc. OOPSLA '89\/} (New Orleans: Oct. 1-6, 1989),
SIGPLAN Notices 24 (10), pp. 103-112.

	-Very similar to the work of Kafura & Lee mentioned above,
	 though slightly more elegant.

I hope people find this summary useful.  Thanks again to all those who
replied.
						Ken