Topic: optimistic update for concurrency control

topics > computer science > database > Group: distributed database

change notification
error safe systems
information as a hint
lock-free concurrency
managing shared memory
reliability of distributed systems
undoing actions in a UserInterface
updating information in a distributed system
updating information in Clearinghouse and Grapevine
updating information with locking
using hypertext for cooperative work


In cooperative work, an optimistic update protocol is often justified since conflicts are rare. There are several options when a conflict occurs. The conflict can be ignored because stale data is harmless, the data can be manually merged, the operations can be reversed, or the latest data can be located. (cbb 7/93)
Subtopic: hardware shared memory up

Quote: survey of consistency models for hardware-based shared memory systems; includes programmer-centric view of relaxed consistency models [»adveSV12_1996]

Subtopic: relaxed memory model up

Quote: relaxed memory consistency models differ in how they relax program order and write atomicity; e.g., a read may return another processor's write before it is globally visible [»adveSV12_1996]
Quote: relaxed memory consistency models often provide a fence instruction or other safety net to force synchronization; these allow compilers to safely optimize large regions of code [»adveSV12_1996]
Quote: programmers can identify synchronization and data operations in performance-critical areas for weak order optimization; example of programmer-centric approach to relaxed memory consistency [»adveSV12_1996]
Quote: Bayou supports four session guarantees: read your writes, monotonic reads, writes follow reads, and monotonic writes; allows self consistency [»edwaWK10_1997]

Subtopic: relaxed concurrency control up

Quote: review concurrency control methods with reduced lock contention, indices, aggregate data, transactions, relaxed queries

Subtopic: write atomicity up

Quote: write atomicity if writes to the same location are serialized and reads are disallowed until the write is visible to all processors [»adveSV12_1996]

Subtopic: locking not needed up

Quote: in very large databases, locking is not necessary since conflicts are rare [»akscRM5_1984]
Quote: KMS users rarely modify the same frame at the same time [»akscRM7_1988a]
Quote: informal locking in KMS by writing an 'in use' item [»akscRM7_1988a]

Subtopic: locking when needed up

Quote: Colab broadcasts changes with optimistic update (voice locks when needed) [»stefM1_1987]

Subtopic: dummy lock up

Quote: optimistic concurrency control by dummy locks for detecting transaction failures; allows long-term transactions [»haliU7_1991]

Subtopic: rollback up

Quote: lookahead-rollback synchronization--execute until a conflict is discovered then roll back the offending processes and reexecute [»jeffDR7_1985]

Subtopic: tentative write up

Quote: Bayou identifies stable and tentative writes. Tentative writes may be re-executed if earlier writes are received [»edwaWK10_1997]

Subtopic: stale data up

Quote: in ADMS+-, updates are logged but not broadcast; if an access path is outdated, it is updated and cached; low cost [»rousN12_1986]
Quote: V's name cache flushes stale data when detected by using that data [»cherDR3_1988]
Quote: in some applications, can detect stale data on use and recover by locating a correct copy [»cherDR5_1986]
Quote: in some applications, cached data may be slightly out of date [»cherDR5_1986]
Quote: if 'almost up-to-date' data is ok, ADMS- will process a query on the workstation without waiting for current updates [»rousN12_1986]
Quote: a data fetch may be optional; e.g., an application could extrapolate, substitute, or forward a request [»cherDR5_1986]
Quote: a relaxed fetch operation may return stale data, incorrect data, or "don't know" [»cherDR5_1986]
Quote: a relaxed store operation may discard the store because of update conflicts

Subtopic: recovery unit up

Quote: optimistic recovery for distributed system via repeatable, message-driven recovery units; reconstruct consistent state after failure [»stroRE8_1985]
Quote: roll-back initiates a state interval of a recovery unit; messages between recovery units define a partial order of state intervals [»stroRE8_1985]
Quote: Bayou uses optimistic concurrency control; a write consists of an update set and a dependency check that calls a merge procedure on failure [»edwaWK10_1997]

Subtopic: timestamp up

Quote: with time-split b-trees, read-only transactions only need a timestamp for concurrency control; ignores all later records [»lomeD6_1989]
Quote: if an analysis uses an item that becomes modified, the former value has a timestamp to limit its validity [»shavMJ2_1980]

Subtopic: manual conflict resolution up

Quote: if update conflict, KMS creates a new frame for manual recovery [»akscRM7_1988a]
Quote: KMS checks for update conflicts when frame is first modified [»akscRM7_1988a]
Quote: before release, need to merge bug fixes into main development work; DSEE provides a multi-window interactive merge command to help automate the process [»leblDB5_1984]
Quote: Cedar isolates changes by requiring an explicit request to merge changes into your version [»leblDB5_1984]

Subtopic: reversible execution up

Quote: with reversible operations, execute immediately and redo if conflict [»sariS10_1985]

Subtopic: ignore conflicts up

Quote: applications may tolerate lost or revoked store operations; e.g., if fetched and stored values are not compared [»cherDR5_1986]

Subtopic: handling conflicts up

Quote: either allow synchronization to back out a user's changes or propagate just the non-conflicting changes; the later is better for unsupervised reconciliations [»fostJN8_2005]
Quote: a syncronizer should be safe, maximal, and schema preserving; do not back out changes; do not make up content; do not propagate conflicts

Related Topics up

Topic: change notification (19 items)
Topic: concurrency (33 items)
Topic: error safe systems (76 items)
Topic: information as a hint (18 items)
Topic: lock-free concurrency (8 items)
Topic: managing shared memory (74 items)
Topic: reliability of distributed systems (35 items)
Topic: undoing actions in a UserInterface (23 items)
Topic: updating information in a distributed system (50 items)
Topic: updating information in Clearinghouse and Grapevine (11 items)
Topic: updating information with locking (20 items)
Topic: using hypertext for cooperative work
(9 items)

Updated barberCB 3/06
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.