Introduction to Distributed Systems

Introduction to Distributed Systems

• Distributed systems are a group of independent computers that are connected through a network and collaborate to achieve a common goal.

Examples of Distributed Systems

• E-commerce websites
• Cloud computing platforms
• Social media networks

Resource Sharing and the Web Challenges

• Sharing resources across multiple computers can be challenging due to issues like concurrency control, data consistency, and fault tolerance.
• The web presents unique challenges for distributed systems as it involves geographically dispersed users and resources.

Architectural Models

• Client-server architecture: A central server provides resources to multiple clients.
• Peer-to-peer architecture: All nodes in the system are equal and can share resources with each other.

Fundamental Models

• Message passing: Communication between nodes occurs through passing messages.
• Shared memory: Nodes communicate by sharing data in a common memory space.

Theoretical Foundation for Distributed System: Limitation of Distributed system

• Absence of global clock: Nodes in a distributed system don't have access to a shared, synchronized clock, making it difficult to coordinate actions across different nodes.
• Shared memory: Implementing shared memory in a distributed system is challenging due to network latency and potential inconsistencies.

Logical Clocks

• Logical clocks are used to provide a consistent ordering of events in a distributed system without relying on a shared clock.
• Lamport's logical clock: A logical clock that uses a counter to assign timestamps to events.
• Vector logical clocks: A more sophisticated logical clock that tracks the timestamps of all nodes involved in an event.

Concepts in Message Passing Systems

• Causal order: Ensuring that messages are delivered in an order that respects the causal relationship between events.
• Total order: Ensuring that all messages are delivered in the same order to all nodes.
• Total causal order: Combining causal order and total order to guarantee both concepts.

Techniques for Message Ordering

• Causal ordering of messages: Techniques like timestamps and vector clocks can be used to achieve causal order.
• Global state: capturing the state of all nodes and messages in a distributed system at a specific point in time is important for debugging and analysis.
• Termination detection: Detecting when all nodes in a distributed system have finished their tasks is a critical function for applications like parallel processing and distributed algorithms.

Distributed Mutual Exclusion

• Classification: Distributed mutual exclusion algorithms can be classified into token-based and non-token-based approaches.
• Requirements: Mutual exclusion algorithms need to guarantee that only one process can access a critical section at a time, preventing data corruption and ensuring fairness.
• Token-based algorithms: They involve passing a token among processes to grant access to the critical section.
• Non-token-based algorithms: These algorithms use other mechanisms, such as timestamps or logical clocks, to achieve mutual exclusion.
• Performance metrics: Latency, throughput, and message complexity are critical performance metrics for distributed mutual exclusion algorithms.

Distributed Deadlock Detection

• System model: Distributed deadlock detection algorithms are crucial for preventing resource starvation and ensuring efficient resource utilization in distributed systems.
• Resource vs. communication deadlocks: Deadlocks can occur due to contention for resources or due to communication dependencies between processes.
• Deadlock prevention: Algorithms that prevent potential deadlocks by restricting resource allocation patterns.
• Deadlock avoidance: These algorithms dynamically monitor system state and avoid potential deadlock situations based on resource allocation strategies.
• Deadlock detection and resolution: Algorithms that identify deadlocks after they occur and then propose strategies to resolve them.
• Centralized deadlock detection: A single node coordinates the detection process by collecting information from other nodes.
• Distributed deadlock detection: Algorithms that distribute the detection responsibility among all participating nodes, reducing communication overhead and improving fault tolerance.
• Path pushing: A distributed deadlock detection technique that involves propagating information about resources and processes through the system.
• Edge chasing: Another distributed deadlock detection technique that focuses on identifying cycles in the resource allocation graph to detect deadlocks.

This quiz explores the fundamental concepts of distributed systems, including their architectural models and challenges. You will learn about resource sharing, message passing, and the unique issues presented by web-based systems. Test your knowledge on e-commerce, cloud computing, and social media networks.