Some informal thoughts on

Shared State in Distributed Systems

Michael L. Scott
Professor and Chair
Computer Science Department
University of Rochester
Rochester, NY 14627-0226
Michael Scott's email address
phone (585) 275-7745, 5478; fax 461-2018

Many distributed applications devote significant effort to maintaining consistent copies of dynamic information at multiple sites. Examples include

These applications differ in

All, however, share the notion of an object (call it a ``segment'') that is read and/or written at multiple sites. I suggest that we recognize this commonality, and embed it in a standard set of mechanisms for binding to shared segments. If we do it right, we'll make it easier to re-use code and run experiments, and we'll defer to the standard on a lot of extraneous issues (e.g. naming and access control).

Related Work

The standardization task would draw on work in several areas, including

network protocols
Just as one specifies a communication protocol when binding to a socket, one ought to be able to specify a sharing protocol when binding to a segment. It probably makes sense to leverage the set-up conventions of the message-passing world wherever possible.
distributed file systems
DFSes already deal with caching and consistency. In many cases, it probably makes sense to think of a shared segment as a memory-mapped file. Among other things, the DFS system community knows how to do access control.
software distributed shared memory
Distributed file systems don't deal much with fine-grain access or with concurrency control among multiple writers. S-DSM systems do.
distributed databases
Like S-DSM, distributed databases deal with fine-grain access and concurrency control. The database community knows how to handle replication, resilience, and nested transactions. They have a very structured view of data, however, which isn't appropriate for all applications.

Protocols and Programming Models

The S-DSM community uses the word ``protocol'' somewhat loosely, to encompass both the user interface and consistency model on the one hand (let's call this the ``programming model''), and the underlying implementation on the other (let's call this the ``underlying protocol''). Examples of programming models include

These models are not necessarily mutually exclusive (garbage collection, for example, is compatible with several of the other models). Several of them (the last one in particular) admit multiple underlying protocols. I don't believe it will be possible (or even desirable) to standardize on a single model. Some applications, for example, will want complete control over the timing of state dissemination. A friend in the CSCW community tells me he doesn't want any state distributed until the human user says so.

Hooks

In principle, an application that conforms to a given programming model should be able to work on top of any compatible underlying protocol. All that matters is that the application invoke the appropriate ``hooks'' in a library that conforms to the underlying protocol. It may even be possible for two appliations that share a segment to use different underlying protocols, though I doubt this will often be the case. Possible hooks include

A binding operation would need to install hooks for implicitly-activated protocol operations (page fault handlers) and return pointers to application-activated operations (put and get, commit and abort, critical-section brackets). I'm not sure how to classify things like allocate, make_ref, drop_ref, acquire, and release.

Naming

Segments should perhaps be named with URLs:

dsbp://www.foo.org/bar

(dsbp = distributed sharing binder protocol)

When creating a segment, one would have to specify the protocol(s) via which it could be accessed. When binding to a segment, one would have to specify a matching protocol. In some cases protocol code (in Java, for example) could be returned by the DSBP server. This is dicey, however, for operations that need to make non-trivial changes to local system state (e.g. changing page protections).

Other Issues


To Michael Scott's home page

To the URCS Home Page

Last Change: 18 July 1997 / Michael Scott's email address