CCS 3103: The Synchronization Process, Mutual Exclusion, and Atomic Transactions

This flashcard set covers the synchronization process in distributed systems, including various clock algorithms, mutual exclusion methods, atomic transaction protocols, and strategies for handling deadlocks.

Synchronization

The coordination of actions among multiple processes to ensure they work in a timely and orderly manner, maintaining concurrency, consistency, and correctness.

Clock Synchronization

The process of ensuring all processes in a system agree on the time, which is vital for logging events and sequencing transactions.

Event Synchronization

A mode of synchronization that coordinates the execution of events across different processes to ensure a particular order, such as in real-time video streaming.

Data Synchronization

Ensuring that the same data is consistently available across different nodes in a distributed system to maintain integrity, often used in cloud storage services.

Clock skew

The time difference that occurs between clocks on different computers within a system.

UTC (Coordinated Universal Time)

The current universal time standard that serves as the basis for all modern civil timekeeping.

External Synchronization

The process of synchronizing a computer's clock with an authoritative, external source of time.

Internal Synchronization

The process of synchronizing a computer’s clock with other computers' clocks within the system to a known degree of accuracy.

Cristian’s Algorithm

A centralized external synchronization algorithm where machines request time from a server and calculate propagation time as $P = (Reply\_time - Request\_time)/2$.

Berkeley Algorithm

A distributed internal synchronization algorithm where a master node polls other nodes for their time discrepancies and tells everyone how to adjust their clocks to the average.

Network Time Protocol (NTP)

A protocol used for clock synchronization of computers over packet-switched, variable-latency networks using a symmetric mode for highest accuracy.

Race Conditions

A challenge in synchronization where multiple processes attempt to access shared resources at the same time, potentially leading to data inconsistency.

Deadlock

A situation where processes are waiting indefinitely for each other to release resources, causing the system to halt.

Starvation

A condition where some processes never gain access to resources because other processes continually monopolize them.

Lamport’s Logical Clocks

A timestamping method used to order events in a distributed system based on a "happens-before" relation ($\rightarrow$) rather than real current time.

Vector Clocks

An extension of logical clocks where each process maintains a vector of timestamps to provide a more accurate way to track causality between events.

Election Algorithms

Algorithms used in distributed systems to determine a new coordinator if the current single coordinator process fails.

Bully Algorithm

An election algorithm where a process initiates an election by sending messages to processes with higher IDs; eventually, the process with the highest identifier becomes the coordinator.

Mutual Exclusion (Mutex)

The property of ensuring that only one process at a time can access a shared resource or a critical section of code.

Semaphores

A synchronization mechanism used in single-processor systems to control access to shared resources and prevent race conditions.

Monitors

A programming construct containing shared data and procedures that automatically allows only one process to execute inside it at a time.

Ricart-Agrawala Algorithm

A distributed mutual exclusion algorithm that uses Lamport’s logical clocks to decide which process enters a critical region based on timestamped request messages.

Token Ring Algorithm

A mutual exclusion method where processes are organized in a logical ring and a token is passed around; a process can only access a critical region when it holds the token.

Atomic Transactions

A sequence of operations executed as a single, indivisible unit where either all operations are performed successfully or none are completed.

ACID Properties

The four required properties of transactions: Atomicity (all-or-nothing), Consistency (valid state transitions), Isolation (no interference), and Durability (permanent changes).

Write-ahead Log

An implementation of transactions where records of changes (old and new values) are written to a log before the actual file blocks are modified to allow for "rollback."

Two-Phase Commit (2PC) Protocol

A distributed transaction protocol consisting of a Voting Phase (coordinator asks participants if they can commit) and a Commit Phase (transaction is committed only if all vote "Yes").

Three-Phase Commit (3PC)

An extension of 2PC that adds a Preparation Phase between voting and committing to avoid system blocking and improve fault tolerance.

Paxos Consensus Algorithm

An algorithm used to achieve consensus across a group of processes in distributed systems, ensuring atomicity even if some nodes fail.

Optimistic Concurrency Control

A method that allows processes to proceed without locks, only checking for problems at the end of the transaction; it is deadlock-free but may require transactions to be re-run if conflicts occur.

Communication Deadlock

A type of deadlock that occurs when processes are waiting on messages from each other in a circular chain, such as process A waiting for B, B for C, and C for A.

Ostrich Algorithm

A strategy for handling deadlocks by simply ignoring the problem, often used because it requires no effort.

Clock Drift

Small differences in the local clocks of different processes that can accumulate over time and lead to synchronization errors.