Topic: updating information in a distributed system

topics > computer science > database > Group: distributed database

broadcasting information
data caching
database change management
database consistency and reliability
database transactions
file cache
information as a hint
implementing distributed systems and applications
heterogeneous database
log-structured rollback-recovery
merging changes
optimistic update for concurrency control
reliable broadcast
replicated data
revision delta
shared information for collaborative work
software maintenance and testing of distributed systems
updating information in Clearinghouse and Grapevine
updating information with locking
updating information with rumor mongering and random updates
version control
version identification


A distributed system stores data in multiple locations. How are changes propagated?

A database can store the master copies and replicate the data as needed. Immutable data may be cached remotely.

Techniques include publish-subscribe, optimisitic replication, timestamps, temporaryly consistent views, caching, leased updates, distributed transactions, log files, distributed garbage collection, type migration.

Other topics discuss reliable broadcast, replicated data, locking, rumor mongering, random updates, version control, and heterogeneous databases.

Fully distributed data is difficult to keep consistent. Conflicting updates require manual intervention. Distributed databases may lead to long transactions or deadlock. (cbb 8/06)

Subtopic: information dissemination up

Quote: propagation good for information dissemination
Quote: use electronic meeting room and publish-subscribe spreadsheets for collaborative, space mission proposals; good predictions [»markG6_2002]
Quote: need discipline of relational model to share large quantities of data by non-programmers acting independently

Subtopic: stale and updated data up

Quote: stale data is OK; most data is updated infrequently or not at all; allows lazy replication and scalability [»boswA10_2005]
Quote: XML should indicate nearly, static elements; simplifies update of stale data [»boswA10_2005]
Quote: Atom XML is a container (feed) of unorder entry elements; must include id, updated, and title; any other elements OK [»boswA10_2005]
Quote: can reliably replace Atom entries with the same and [»boswA10_2005]
Subtopic: problem of related data up

Quote: keeping two related, but different sets of data is asking for trouble; sooner or later someone will get them out of sync [»koenA12_1995]
Quote: simultaneous, conflicting updates indicate an external coordination problem [»oppeDC10_1981]

Subtopic: service orientation up

Quote: prohibit database access by clients; simplifies scaling and reliability updates of services [»grayJ5_2006]

Subtopic: optimistic replication up

Quote: survey of optimistic replication algorithms; background propagation of change; supports concurrent work and allows for unreliable communications [»saitY3_2005]

Subtopic: deterministic, asynchronous updates up

Quote: a set of asynchronous updates uniquely define a state if update is total, commutative, and idempotent [»lampBW8_1985]
Quote: concurrent use of replicating persistence requires synchronized extern and intern operations [»buneP5_1986]

Subtopic: timestamp algorithms up

Quote: update name directory copies by point-to-point messages backed by a global sweep for all updates before some time-stamp [»lampBW8_1985]
Quote: update a name directory value by giving a path to the value with timestamps for each internal node; can make the update order immaterial [»lampBW8_1985]

Subtopic: network partition, disconnection up

Quote: can run disconnected from a network if cache data; allows one to two day disconnections; update afterwards in a minute [»kistJJ2_1992]
Quote: few update conflicts across network partitions caused by optimistic server replication; over nearly a year [»kistJJ2_1992]

Subtopic: temporally consistent views up

Quote: the priority ceiling protocol may be extended to real-time databases with transactions; allows schedule analysis and temporally consistent views [»rajkR_1991]

Subtopic: database replication up

Quote: use 0-safe database replication where no copy is consistent and up-to-date; use subtransactions to update remote copies; e.g., Den Danske Bank [»franL12_1999]
Quote: eager update everywhere replication serializes conflicting transactions via total order multicast of batched updates at commit; reduce conflicts with snapshot isolation and short message delays [»kemmB9_2000]
Quote: incremental computation of database updates using comprehension syntax; maintains consistency while updating a value; efficient, strict or lazy updates [»nakaH10_2001]

Subtopic: linked directories up

Quote: determine all copies of a name directory by linking them a ring; update by splicing and rebuild by defining a new epoch [»lampBW8_1985]

Subtopic: page and object servers up

Quote: a data-shipping system may use page servers for 4-8 kbyte pages or variable length object servers [»franMJ9_1997]

Subtopic: shared variables up

Quote: define shared variables over the Internet with reload and update operations [»harrJ10_1998]

Subtopic: data cache up

Quote: classify cache-consistency by whether it detects or avoids stale data
Quote: in a data-shipping architecture, the client manages all requests and cached data [»franMJ9_1997]
Quote: under pessimistic approaches, avoidance of stale cached data typically sends far fewer messages than detection schemes; also more efficient use of client cache [»franMJ9_1997]
Quote: under an optimistic approach, invalidating remote copies was more robust than propagating changes [»franMJ9_1997]
Quote: least-unified value algorithm for cache replacement of distributed, non-uniform data objects; robust and efficient [»bahnH6_2002]
Quote: ADMS+- has an incremental access model: it reuses previously found access paths to data [»rousN12_1986]
Quote: in ADMS+-, updates are logged but not broadcast; if an access path is outdated, it is updated and cached; low cost [»rousN12_1986]

Subtopic: primary site for updates up

Quote: primary-site responsible for propagating all of its updates, e.g., DARPA [»demeA8_1987]
Quote: users initiate directory updates that the telephone company installs [»oppeDC7_1983]
Quote: run model calculations on a central machine to give its author control over program maintenance [»gammR_1982]
Quote: every change to ADMS+ data relations are recorded on a backlog for transmission to ADMS- workstations [»rousN12_1986]
Quote: since ADMS- caches updates, it only needs the latest updates to a relation from ADMS+ [»rousN12_1986]
Quote: GenBank satellite databases are updated by email submissions similar to researcher submissions [»cinkMJ5_1991]

Subtopic: leased updates up

Quote: use leases to maintain order across replicas; master grants a chunk lease to the primary replica, and the primary orders the mutations [»gherS10_2003]

Subtopic: safe, type migration up

Quote: hot swap modules need to change types while preserving type safety; use reflective mechanism with programmer-defined version adapters [»duggD9_2001]
Quote: a version adapter maps a value from the old to new version of a type; use run-time type tags to identify versioned types [»duggD9_2001]

Subtopic: conflicting change 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]

Subtopic: synchronization across different schemas up

Quote: synchronize disparate schemas using bi-directional, tree transforms (lenses) from input trees to synchronization schemas; controls alignment of information and identifies conflicts [»fostJN8_2005]
Quote: a state-based synchronizer depends only on the common ancestor state and current state; for loosely coupled, XML data [»fostJN8_2005]

Subtopic: distributed garbage collection up

Quote: taxonomy of distributed garbage-collection schemas; explores locality, overhead, and latency [»abduSE9_1998]
Quote: both distributed and normal garbage collection must balance completeness and expediency; difficult to do if distributed [»abduSE9_1998]

Subtopic: group commit up

Quote: Cedar uses group commit to log multiple updates together; done every half second [»hagmR_1987]

Subtopic: log files for updates up

Quote: write changes of the file name table and leader pages to a redo log; recovery in about two seconds; log entry format [»hagmR_1987]
Quote: Cedar divides its circular log file into thirds; on entering a new third, Cedar flushes modified data not logged elsewhere; recorded in header [»hagmR_1987]

Subtopic: file update statistics up

Quote: if exclude system files, 99.5% of all changes to a file are by the previous writer [»kistJJ2_1992]
Quote: if exclude system files, the chance of different users modifying the same object within a week is less than 0.4%

Related Topics up

Topic: broadcasting information (18 items)
Topic: data caching (35 items)
Topic: database change management (12 items)
Topic: database consistency and reliability (15 items)
Topic: database transactions (27 items)
Topic: file cache (23 items)
Topic: information as a hint (18 items)
Topic: implementing distributed systems and applications (41 items)
Topic: heterogeneous database (6 items)
Topic: log-structured rollback-recovery (13 items)
Topic: merging changes (7 items)
Topic: optimistic update for concurrency control (35 items)
Topic: reliable broadcast (29 items)
Topic: replicated data (51 items)
Topic: revision delta (18 items)
Topic: shared information for collaborative work (36 items)
Topic: software maintenance and testing of distributed systems (16 items)
Topic: timestamps (19 items)
Topic: updating information in Clearinghouse and Grapevine (11 items)
Topic: updating information with locking (20 items)
Topic: updating information with rumor mongering and random updates (13 items)
Topic: version control (34 items)
Topic: version identification
(12 items)

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