Chapter 5:  Synchronization, WWV

Logical clocks (a thread can be stopped and started at any time:
bullet Lamport timestamps (a happens before b) Totally-ordered multicast (all messages are delivered in the same order)
bullet

Vector timestamps (causality)( causal consistency)

 

Logical clocks are clocks used in asynchronous distributed systems for ordering events since there are no global physical clocks available. Logical clocks could be built using total ordering (Lamport ordering) or partial ordering (Vector ordering).

 

Global state:  (local state of each process with the messages that are currently in transit)

bulletlocal state of each process
bullet

messages in transit

Snapshot is taken from an asynchronous system.

 

Election algorithms:  Distributed algorithm

bullet Bully algorithm (highest ID bully the others to submission, messages sent across and not in a ring)
bulletRing algorithm (does not use a token, messages are sent to the next in the ring)

Clock scew (between to clocks) and clock drift (between a clock and a master clock)

Berkley algorithm:  A Daemon tell the processes to adjust their clocks.

5.5  Mutual exclusion :  Critical sections of code accessing shared data must be protected, only one process at a time can access shared resources like a file or a printer etc.

 

In single-processor systems, critical regions are protected using monitors.

In distributed systems it is done differently

 

bulletCentralized algorithm (the coordinator is not replying, which will block process #2 entering the critical region)
bulletDistributed algorithm (Lamports' timestamp algorithm adding 1, comparing timestamps and Vectors)(process builds a message containing the name of critical region, process  number and the current time 1. any process answers and says either OK, 2. does not reply and queues the rquest 3. the lowest timestamp wins either OK to the process or nothing like 1. and 2.
bullet

A token ring algorithm (The process having the token can enter the critical region, the token is passed around in the ring, the processes are arranged in a ring)

 

Comparison:

bullet

The centralized algorithm is simplest and also most efficient.  Requires only 3 messages to enter and a release to exit.  Delay: 2

bullet

Distributed requires n-1 request messages and an additional n-1 grant messages (totally 2(n-1)). Delay: 2(n-1)

bulletToken ring needs 1 to many messages.  Delay: (0 to (n-1)

Critical region: part of a code that requires exclusive access to resources, piece of code that can only be executed by one process or thread at a time.

5.6  Distributed transactions (Transaction:  Single logical operation on the data):

bullet

Flat transactions (does not alow partial results to be committed or aborted, use ACID)

bullet

Nested (constructed from a number of sub-transactions, top level with children)

bullet

Distributed (same as nested, but flat and not a hiarchy)

bullet

Implementation (private workspace for the process and writeahead log where everythings is written in a log ahead of the actual change to the file)

bullet

Concurrency control (serializability, two-phase-locking for reading or writing data)(coordination of access to resources)

bullet

Pesimistic and optimistic timestamp ordering using Lamport

 

ACID: Key transaction processing features of a database management system.  Without ACID, the integrity of the database can not be guaranteed.  Either all or nothing when it comes to transaction.

 
Atomic: To the outside world the transaction happens without dividing the transaction up in part.  It happens as a whole

Consistent: The transaction does not viaolate system invariants

Isolated: Concurrent transactions do not interfere with each other.

Durable:  Once the transaction commits, the changes are permanent.