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

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

• conventional web pages being read by multiple clients
• ``push'' style web pages being sent to multiple clients
• blackboards in computer-supported collaborative work
• cached copies of open files in a distributed file system
• file replicas in a fault-tolerant or highly-available file system
• pages in a software distributed shared memory system
• frames in a distributed virtual memory
• records in an on-line transaction-processing system
• video windows in a tele-conferencing system

These applications differ in

• operations on the shared object required by the application
• degree of sharing
• consistency model
• level of performance required (bandwidth, latency, predictability)
• level of fault-tolerance required

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

• Associate reader-writer locks with segments. Read and write a segment with ordinary loads and stores, but only when in posession of the appropriate lock.
• Read and write a segment with explicit put and get operations; assume that synchronization is handled independently by the applications.
• Read and write with explicit put and get operations, in conjunction with nested commit-abort style transactions.
• Treat the segment as a heap, with automatic distributed garbage collection.
• Identify acquire and release operations in the program, and refrain from data races (permitting the implementation of release consistency).

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

• synchronization operations that bracket a critical section in which a segment is accessed (e.g. reader-writer lock acquires and releases)
• acquires and releases of synchronization objects, without respect to particular segments (for release consistency)
• page faults (for VM-based software DSM)
• put, get, commit, abort
• allocate, make_ref, and drop_ref routines for a garbage-collected heap segment

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

• How do we deal with heterogeneous data representations? (cross-machine, cross-language)
• How do we integrate long-distance sharing protocols with local-area protocols? Imagine, for example, a simulation running on a local S-DSM cluster, with a remote front end that needs to read, or even write, simulation data structures.
• If we embed pointer-rich data structures in segments, they need to be mapped at the same address in every user. How do we parcel out addresses to prevent conflicts? 64-bit address spaces help, but probably don't solve the problem.

To Michael Scott's home page

To the URCS Home Page

Last Change: 18 July 1997 /