Distributed Systems in Computer Science
Explore the concepts of distributed systems in computer science, covering issues, advantages, examples of problems, design challenges, and models for distributed algorithms. Discover the complexities and solutions in this fascinating field.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Introduction CS60002: Distributed Systems Pallab Dasgupta Professor, Dept. of Computer Sc. & Engg., Indian Institute of Technology Kharagpur 1 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Books Advanced Concepts in Operating Systems Mukesh Singhal and Niranjan G. Shivaratri McGraw Hill International Edition Introduction to Distributed Algorithms Gerard Tel Cambridge University Press Available in the CSE Dept Library (Acc No: I-455) 2 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
What is a distributed system? A very broad definition: A set of autonomous processes communicating among themselves to perform a task Issues: Un-reliability of communication Lack of global knowledge Lack of synchronization and causal ordering Concurrency control Failure and recovery 3 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Advantages Resource Sharing Higher Performance Fault Tolerance Scalability 4 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Examples of problems Reliable communication Theoretically impossible? Muddy forehead and related problems Concurrency problems 5 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Example: Automotive Control Source: Leen and Hefferman, IEEE Computer, Jan 2002 6 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Why is it hard to design them? The usual problem of concurrent systems: Arbitrary interleaving of actions makes the system hard to verify + No globally shared memory (therefore hard to collect global state) No global clock Unpredictable communication delays 7 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Models for Distributed Algorithms Topology: Completely connected, Ring, Tree etc. Communication: Shared memory / Message passing (reliable? Delay? FIFO/Causal? Broadcast/multicast?) Synchronous/asynchronous Failure models: Fail stop, Crash, Omission, Byzantine An algorithm needs to specify the model on which it is supposed to work 8 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Complexity Measures Message complexity: no. of messages Communication complexity / Bit Complexity: no. of bits Time complexity: For synchronous systems, no. of rounds For asynchronous systems, different definitions are there. 9 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Some Fundamental Problems Ordering events in the absence of a global clock Capturing the global state Mutual exclusion Leader election Clock synchronization Termination detection Constructing spanning trees Agreement protocols 10 INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
