Topic: concurrency control by sequencers

topics > computer science > Group: distributed systems

distributed database
concurrency control by monitors
critical regions
function call
implementing distributed systems and applications
index sequence for array access
synchronized processing


Interacting multi-processors will retain consistency if sequence constraints are followed. Unique sequences can be generated by a time clock with location stamp. This is analogous to the ticket machines found in bakeries and butcher shops. Sequencers can provide synchronization for distributed database updates. They allow local modification without global synchronization. (cbb 5/80)
Subtopic: serializer, global virtual clock up

Quote: a serializer should prevent all other access to a protected resource [»atkiR_1977]
Quote: serializability only requires some serial order is equivalent to an interleaved operation [»bernPA5_1978]
Quote: a distributed system can use a global virtual clock for synchronization and global progress [»jeffDR7_1985]
Quote: V uses time servers to serialize access to resources; better than monitors since independent of client [»cherDR4_1984]
Quote: CBCAST for casual broadcast to maintain a partial ordering system wide [»birmKP2_1987]

Subtopic: assigned order up

Quote: synchronization by controlling the sequence of significant events instead of by using mutual exclusion [»reedDP2_1979]
Quote: with a serializer, processes do to have to signal other processes
Quote: with a serializer, the condition for resuming execution is explicitly stated when entering a queue [»atkiR_1977]
Quote: a sequencer assigns an order to events occurring in the system
Quote: reliable notification by a logger process that handles all messages; logs messages; adds an issue number to published notices (archived) [»cherDR4_1984]

Subtopic: event counts up

Quote: an eventcount is a communication path for signaling and observing the progress of concurrent computations [»reedDP2_1979]
Quote: eventcount solutions to synchronization often avoid multiple writers to the same variable [»reedDP2_1979]
Quote: producer/consumer synchronization uses eventcounts to maintain the relative ordering; instead of mutual exclusion [»reedDP2_1979]

Subtopic: tickets up

Quote: a sequencer delivers a non-decreasing integer for each ticket(s) operation [»reedDP2_1979]
Quote: sequencers use a ticket operation that mimics the automatic ticket machines used in bakeries [»reedDP2_1979]
Quote: unlike eventcounts, a sequencer does not allow concurrent ticket operations [»reedDP2_1979]

Subtopic: roll-back up

Quote: lookahead-rollback synchronization--execute until a conflict is discovered then roll back the offending processes and reexecute [»jeffDR7_1985]
Quote: if a process receives an earlier message, it rolls-back and sends out antimessages to cancel its recent communications [»jeffDR7_1985]
Quote: in Time Warp, every message has an antimessage that annihilates it if both are in the same queue [»jeffDR7_1985]

Subtopic: distributed update up

Quote: a single transaction generates one local action followed by as many update actions as there are sites [»bernPA5_1978]
Quote: site n updates its local copy of a data item iff its local timestamp is older than the requesting transaction's timestamp [»bernPA5_1978]
Quote: a site requesting an update action, waits for ACCEPT messages with later timestamps from all other sites; ensures all up-to-date [»bernPA5_1978]
QuoteRef: bernPA5_1978 ;;157 four different protocols for different levels of synchronization; simplest depends on pipelined messages
Quote: with protocol's P2 & P3, a site broadcasts an update request; while waiting, it can process unrelated transactions [»bernPA5_1978, OK]
Quote: SDD-1 assigns a transaction protocol by a protocol table that embodies a detailed analysis of how classes interfere with each other [»bernPA5_1978]

Subtopic: update problems up

Quote: cache coherence by ordering writes to the same location does not satisfy sequential memory consistency since different locations may use different orderings [»adveSV12_1996]

Subtopic: crowds vs. counters up

Quote: if use crowds instead of counters for synchronization, can determine which processes are currently using a resource

Related Topics up

Group: distributed database   (6 topics, 194 quotes)
Topic: concurrency (33 items)
Topic: concurrency control by monitors (24 items)
Topic: critical regions (58 items)
Topic: function call (28 items)
Topic: implementing distributed systems and applications (41 items)
Topic: index sequence for array access (16 items)
Topic: synchronized processing (35 items)
Topic: timestamps
(19 items)

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