Course Details

Subject {L-T-P / C} : CS6113 : Distributed Computing { 3-0-0 / 3}

Subject Nature : Theory

Coordinator : Prof. Bibhudatta Sahoo

Syllabus

A model of distributed computations: A distributed program, A model of distributed executions, Models of communication networks, Global state of a distributed system, Cuts of a distributed computation, Past and future cones of an event, Models of process communications.

Logical time: Introduction, A framework for a system of logical clocks, Scalar time, Vector time, Efficient implementations of vector clocks, Jard–Jourdan’s adaptive technique, Matrix time, Virtual time, Physical clock synchronization: NTP.

Global state and snapshot recording algorithms: System model and definitions, Snapshot algorithms for FIFO channels, Variations of the Chandy–Lamport algorithm, Snapshot algorithms for non-FIFO channels, Snapshots in a causal delivery system, Monitoring global state, Necessary and sufficient conditions for consistent global, snapshots, consistent global snapshots in a distributed computation.

Message ordering and group communication: Message ordering paradigms, Asynchronous execution with synchronous communication, Synchronous program order on an asynchronous system, Group communication, Causal order (CO), Total order, A nomenclature for multicast, Propagation trees for multicast, Classification of application-level multicast algorithms, Semantics of fault-tolerant group communication, Distributed multicast algorithms at the network layer.

Termination detection: System model of a distributed computation, Termination detection using distributed snapshots, Termination detection by weight throwing, A spanning-tree-based termination detection algorithm, Message-optimal termination detection, Termination detection in a very general distributed computing model, Termination detection in the atomic computation model, Termination detection in a faulty distributed system.
Distributed mutual exclusion algorithms: Lamport’s algorithm, Ricart–Agrawala algorithm, Singhal’s dynamic information-structure algorithm, Lodha and Kshemkalyani’s fair mutual exclusion algorithm, Quorum-based mutual exclusion algorithms, Maekawa’s algorithm, Agarwal–El Abbadi quorum-based algorithm, Token-based algorithms, Suzuki–Kasami’s broadcast algorithm, Raymond’s tree-based algorithm.

Deadlock detection in distributed systems: System model, Models of deadlocks, Knapp’s classification of distributed deadlock detection algorithms, Mitchell and Merritt’s algorithm for the single resource model, Chandy–Misra–Haas algorithm for the AND model, Chandy–Misra–Haas algorithm for the OR model, Kshemkalyani–Singhal algorithm for the P-out-of-Q model.

Authentication in distributed systems: Protocols based on symmetric cryptosystems, Protocols based on asymmetric cryptosystems, Password-based authentication, and Authentication protocol failures.

Self-stabilization: System model, Definition of self-stabilization, Issues in the design of self-stabilization algorithms, Methodologies for designing self-stabilizing systems, Communication protocols, Self-stabilizing distributed spanning trees, Self-stabilizing algorithms for spanning-tree construction, An anonymous self-stabilizing algorithm for 1-maximal independent set in trees, A probabilistic self-stabilizing leader election algorithm, The role of compilers in self-stabilization, Self-stabilization as a solution to fault tolerance, Factors preventing self-stabilization.

Course Objectives

Course Outcomes

Study software components of distributed computing systems. Know about the communication and interconnection architecture of multiple computer systems. <br />Recognize the inherent difficulties that arise due to distributedness of computing esources. Understanding of networks & protocols, mobile & wireless computing and their applications to real world problems. <br />understand basic problems in distributed computing, especially in relation to concurrency, parallelism, synchronization, deadlocks, safety and liveness properties <br />understand differences between various distributed computing models and widely used distributed computing schemes <br />Understanding communication mechanism among the distributed entities <br />Authentication and self-stabilization issues in distributed system <br />At the end students will be familiar with the design, implementation and security issues of distributed system

Essential Reading

Supplementary Reading