BIRLA
INSTITUTE OF TECHNOLOGY & SCIENCE, PILANI
WORK
INTEGRATED LEARNING PROGRAMMES
Part A: Content
design
|
Academic Term
|
Second Semester 2017-2018
|
|
Course Title
|
DISTRIBUTED COMPUTING
|
|
Course ID No.
|
SS ZG526
|
|
Instructor(s)
|
BARSHA MITRA
|
|
No
|
Course
Objectives
|
|
CO1
|
This course will cover various hardware architectures for
building distributed systems, and their communication models.
|
|
CO2
|
This will help students understand the design aspects of
various software applications that can be deployed on various distributed
systems.
|
|
CO4
|
This will provide an understanding of the complexities and
resource management issues that are critical in building a large-scale
distributed system.
|
|
CO5
|
This course will cover algorithmic aspects of
building/designing distributed systems in domains like IoT, P2P, Cluster,
Grid computing etc.
|
Text Book(s)
|
T1
|
Ajay
D. Kshemkalyani, and Mukesh Singhal “Distributed Computing: Principles,
Algorithms, and Systems”, Cambridge
University Press,
2008 (Reprint 2013).
|
Reference Book(s)
& other resources
|
R1
|
Kai
Hwang, Geoffrey C. Fox, and Jack J. Dongarra, “Distributed and Cloud
Computing: From Parallel processing to the Internet of Things”, Morgan
Kaufmann, 2012 Elsevier Inc.
|
|
R2
|
John
F. Buford, Heather Yu, and Eng K. Lua, “P2P Networking and Applications”,
Morgan Kaufmann, 2009 Elsevier Inc.
|
Content Structure
1.
Introduction
1.1.
Definition
1.2.
Relation to Computer
system components
1.3.
Motivation
1.4.
Relation to parallel
multiprocessor/ multicomputer systems
1.5.
Distributed Communication
models (RPC, …)
1.6. Design issues and
challenges
2.
A model of distributed computations
2.1.
A distributed program
2.2.
A model of distributed
executions
2.3.
Models of Communication
Networks
2.4.
Global state of a
distributed system
2.5.
Cuts of a distributed
computation
3.
Logical time
3.1.
Introduction
3.2.
A framework for a system
of logical clocks
3.2.1.
Definition
3.2.2.
Implementing logical
clocks
3.3.
Scalar time
3.3.1.
Definition
3.3.2.
Basic properties
3.4.
Vector time
3.4.1.
Definition
3.4.2.
Basic properties
3.5.
Efficient implementation
of vector clocks
3.5.1.
Singhal-Kshemkalyani’s
differential technique
3.5.2.
Fowler-Zwaenepoel’s
direct-dependency technique
4.
Global state and snapshot recording algorithms
4.1.
Introduction
4.2.
System model and
definitions
4.2.1.
System model
4.2.2.
A consistent global state
4.2.3.
Interpretation in terms of
cuts
4.2.4.
Issues in recording a
global state
4.3.
Snapshot algorithms for
FIFO channels
4.3.1.
Chandy-lamport algorithm
4.3.2.
Properties of recorded global
state
4.4.
Variations of the
Chandy-lamport algorithm
4.4.1.
Spezialetti-Kearns
algorithm
4.5.
Snapshot algorithms for
non-FIFO channels
4.5.1.
Lai-Yang algorithm
5.
Terminology and basic algorithms
5.1.
Topology abstraction and
overlays
5.2.
Elementary graph
algorithms
5.2.1. Synchronous
single-initiator spanning tree algorithm using flooding
5.2.2.
Asynchronous single-initiator spanning tree algorithm using flooding
5.2.3.
Broadcast and Convergecast on a tree
6.
Message ordering and Group communication
6.1. Group communication
6.2. Causal order (CO)
6.2.1. The Raynal-Schiper-Toueg algorithm
6.2.2. Birman-Schiper-Stephenson protocol
6.2.3. Schiper-Eggli-Sandoz protocol
6.3. Classification of
application-level multicast algorithms
7.
Distributed mutual exclusion
7.1.
Introduction
7.2.
Preliminaries
7.2.1. System model
7.2.2. Requirements of mutual exclusion algorithms
7.2.3. Performance metrics
7.3. Lamport’s algorithm
7.4. Ricart-Agrawala algorithm
7.5. Maekawa’s algorithm
7.6. Suzuki-kasami’s broadcast algorithm
7.7. Raymond’s tree-based algorithm
8.
Deadlock detection in distributed systems
8.1.
Introduction
8.2.
System model
8.2.1. Wait-For-Graph
8.3. Preliminaries
8.3.1. Deadlock handling strategies
8.3.2. Issues in deadlock detection
8.3.3. Models of deadlocks
8.4. Chandy-Misra-Haas algorithm for the AND
model
8.5. Chnady-Misra-Haas algorithm for the OR
model
9.
Consensus and agreement algorithms
9.1.
Problem definition
9.2.
The Byzantine agreement
and other problems
9.3. Consensus algorithm for Byzantine
failures
10.
Peer-to-Peer Computing and Overlay graphs
10.1.
Introduction
10.2.
Napster
10.3.
Data indexing and overlays
10.4.
Unstructured overlays
10.4.1.
Properties
10.4.2.
Gnutella
10.4.3.
Search in Gnutella and
Unstructured overlays
10.5.
Chord distributed hash
table
10.6.
Security concerns in Peer
to Peer networks
10.7.
Internet graphs
10.8.
Generalized random graph
networks
10.9.
Small world networks
10.10.
Scale free networks
11.
Computer clusters for scalable parallel computing
11.1.
Clustering for massive
parallelism
11.2.
Computer clusters and MPP
architectures
11.3.
Design principles of
Computer clusters
11.4.
Cluster job and resource
management
12.
Grid Computing systems and resource management
12.1.
Grid architecture and
service modelling
12.2.
Grid projects and grid
systems built
12.3.
Grid resource management
and brokering
13.
Internet of Things (IoT)
13.1.
The IoT for ubiquitous
computing
13.2.
Radio-Frequency
Identification (RFID)
13.3.
Sensor networks and Zigbee
technology
13.4.
Global positioning system
Learning Outcomes:
|
No
|
Learning Outcomes
|
|
LO1
|
Understanding of middleware platforms like RPC (Sun RPC, etc.)
for implementing communication models over distributed systems.
|
|
LO2
|
Understanding the need of Logical clocks and their usages in
building distributed systems and its’ components.
|
|
LO3
|
Understanding of Mutual exclusion primitives, Agreement
protocols, and deadlock handling scenarios in distributed systems.
|
|
LO4
|
Understanding of search, storage, communication, efficiency
and other related issues in paradigms like P2P, Cluster, Grid, and Internet
of Things.
|
Part B: Course Handout
|
Academic Term
|
Second Semester
2017-2018
|
|
Course Title
|
Distributed
Computing
|
|
Course No
|
SS ZG526
|
|
Instructor
|
Barsha Mitra
|
|
Contact Hours
|
List of Topic Title
(from content structure in Part A)
|
Topic #
(from content
structure in Part A)
|
Text/Ref Book/external resource
|
|
1
|
· Introduction
o Definition
o Relation to Computer system components
o Motivation
o Relation to parallel multiprocessor/ multicomputer systems
o Distributed Communication models (RPC, …)
o Design issues and challenges
|
1
|
T1: Ch-1
|
|
2
|
|||
|
3
|
|||
|
4
|
|||
|
5
|
· A model of
distributed computations
o A distributed program
o A model of distributed executions
o Models of Communication Networks
o Global state of a distributed system
o Cuts of a distributed computation
· Logical time
o Introduction
o A framework for a system of logical clocks
§
Definition
§
Implementing
logical clocks
o Scalar time
§
Definition
§
Basic properties
o Vector time
§
Definition
§
Basic properties
o Efficient implementation of vector clocks
§
Singhal-Kshemkalyani’s
differential technique
§
Fowler-Zwaenepoel’s
direct-dependency technique
|
2, 3
|
T1: Ch-2&3
|
|
6
|
|||
|
7
|
|||
|
8
|
|||
|
9
|
· Global state and
snapshot recording algorithms
o Introduction
o System model and definitions
§ System model
§ A consistent global state
§ Interpretation in terms of cuts
§ Issues in recording a global state
o Snapshot algorithms for FIFO channels
§ Chandy-lamport algorithm
§ Properties of recorded global state
o Variations of the Chandy-lamport algorithm
§ Spezialetti-Kearns algorithm
o Snapshot algorithms for non-FIFO channels
§ Lai-Yang algorithm
|
4
|
T1: Ch-4
|
|
10
|
|||
|
11
|
|||
 12 |
|||
|
13
|
· Terminology and
basic algorithms
o Topology abstraction and overlays
o Elementary graph algorithms
§ Synchronous single-initiator spanning tree algorithm using
flooding
§ Asynchronous single-initiator spanning tree algorithm using
flooding
§ Broadcast and Convergecast on a tree
· Message ordering
and Group communication
o Group communication
o Causal order (CO)
§ The Raynal-Schiper-Toueg algorithm
§ Birman-Schiper-Stephenson protocol
§ Schiper-Eggli-Sandoz protocol
o Classification of application-level multicast algorithms
|
5, 6
|
T1: Ch-5&6
|
|
14
|
|||
|
15
|
|||
|
16
|
|||
|
17
|
· Distributed
mutual exclusion
o Introduction
o Preliminaries
§ System model
§ Requirements of mutual exclusion algorithms
§ Performance metrics
o Lamport’s algorithm
o Ricart-Agrawala algorithm
o Maekawa’s algorithm
o Suzuki-kasami’s broadcast algorithm
o Raymond’s tree-based algorithm
|
7
|
T1: Ch-9
|
|
18
|
|||
|
19
|
|||
|
20
|
|||
|
21
|
· Deadlock
detection in distributed systems
o Introduction
o System model
§ Wait-For-Graph
o Preliminaries
§ Deadlock handling strategies
§ Issues in deadlock detection
§ Models of deadlocks
o Chandy-Misra-Haas algorithm for the AND model
o Chnady-Misra-Haas algorithm for the OR model
·
Consensus and agreement algorithms
o Problem definition
o The Byzantine agreement and other problems
o Consensus algorithm for Byzantine failures
|
8, 9
|
T1: Ch-10&14
|
|
22
|
|||
|
23
|
|||
|
24
|
|||
|
25
|
· Peer-to-Peer
Computing and Overlay graphs
o Introduction
o Napster
o Data indexing and overlays
o Unstructured overlays
§ Properties
§ Gnutella
§ Search in Gnutella and Unstructured overlays
o Chord distributed hash table
o Security concerns in Peer to Peer networks
o Internet graphs
o Generalized random graph networks
o Small world networks
·
Scale free
networks
|
10
|
T1: Ch-18
|
|
26
|
|||
|
27
|
|||
|
28
|
|||
|
29
|
· Computer clusters
for scalable parallel computing
o Clustering for massive parallelism
o Computer clusters and MPP architectures
o Design principles of Computer clusters
o Cluster job and resource management
· Grid Computing
systems and resource management
o Grid architecture and service modelling
o Grid projects and grid systems built
o Grid resource management and brokering
· Internet of
Things (IoT)
o The IoT for ubiquitous computing
o Radio-Frequency Identification (RFID)
o Sensor networks and Zigbee technology
o Global positioning system
|
11,12&13
|
R1: Ch-2,7&9
|
|
30
|
|||
|
31
|
|||
|
32
|
# The above contact hours and topics can be adapted for
non-specific and specific WILP programs depending on the requirements.
Evaluation
Scheme:
Legend: EC = Evaluation Component; AN =
After Noon Session; FN = Fore Noon Session
|
No
|
Name
|
Type
|
Duration
|
Weight
|
Day, Date, Session, Time
|
|
EC-1
|
Quiz-I/ Assignment-I
|
Online
|
-
|
5%
|
February 1 to 10, 2018
|
|
|
Quiz-II
|
Online
|
-
|
5%
|
March 1 to 10, 2018
|
|
|
Quiz-III/ Assignment-II
|
Online
|
-
|
5%
|
March 20-30, 2018
|
|
|
Lab
|
Online
|
-
|
10%
|
March 20-30, 2018
|
|
EC-2
|
Mid-Semester Test
|
Closed Book
|
2 hours
|
30%
|
03/03/2018 (AN) 2 PM TO 4 PM
|
|
EC-3
|
Comprehensive Exam
|
Open Book
|
3 hours
|
45%
|
21/04/2018 (AN) 2 PM TO 5 PM
|
Syllabus for Mid-Semester Test (Closed
Book): Topics in Contact Hours : 1 to 16
Syllabus for Comprehensive Exam (Open
Book): All topics (Session Nos. 1 to 32)
Important links and information:
Elearn portal:
https://elearn.bits-pilani.ac.in
Students are expected to visit the
Elearn portal on a regular basis and stay up to date with the latest announcements
and deadlines.
Contact sessions:
Students should attend the online lectures as per the schedule provided on the
Elearn portal.
Evaluation Guidelines:
1.
EC-1 consists of either two Assignments
or three Quizzes. Students will attempt them through the course pages on the
Elearn portal. Announcements will be made on the portal, in a timely manner.
2.
For Closed Book tests: No books or
reference material of any kind will be permitted.
3.
For Open Book exams: Use of books and
any printed / written reference material (filed or bound) is permitted.
However, loose sheets of paper will not be allowed. Use of calculators is
permitted in all exams. Laptops/Mobiles of any kind are not allowed. Exchange
of any material is not allowed.
4.
If a student is unable to appear for the
Regular Test/Exam due to genuine exigencies, the student should follow the
procedure to apply for the Make-Up Test/Exam which will be made available on
the Elearn portal. The Make-Up Test/Exam will be conducted only at selected
exam centres on the dates to be announced later.
It shall be the responsibility of the
individual student to be regular in maintaining the self study schedule as
given in the course handout, attend the online lectures, and take all the
prescribed evaluation components such as Assignment/Quiz, Mid-Semester Test and
Comprehensive Exam according to the evaluation scheme provided in the handout.
No comments:
Post a Comment