SE 342 Distributed Computing
Department of Computer Science, IIU
Spring 2011
Spring 2011
|
The fundamental beliefs underlying the Honor Code of my classroom are that my student has the right to live in an academic environment that is free from the injustices caused by any form of intellectual dishonesty, and that the honesty and integrity of all members of my classroom contribute to its pursuit for Truth. |
|
Course
StructureLectures = 2 [HEC Recommended 3] Labs = 0 Credit hours = 3
Prerequisites 1. Analysis of Algorithms or Computational Theory 2. Experience in Programming
Course ObjectiveThe course is an introduction to distributed and parallel computing. It gives an overview of distributed/parallel computers, and distributed/ parallel computation. It discusses the basic principles, concepts and techniques used in distributed systems. The course gives the core ideas behind modern coordination paradigms and concurrent data structures. It introduces a variety of methodologies and approaches for reasoning about concurrent computation and algorithms/programs; Identifies techniques to formally prove correctness of multiprocessor algorithms; presents techniques to formally study the progress properties of concurrent algorithms. In addition, in this course we study the techniques to analyze the performance of multiprocessor algorithms.
Course OutlineWhy use parallel and distributed system? Speedup and Amdahl's law; Hardware Architecture: multiprocessors (shared memory), network of workstation (distributed memory), Clusters; Software Architectures: threads and shared memory, processes and message passing, distributed shared memory, distributed shared data; Parallel Algorithms; Concurrency and Synchronization; Data and work partitioning; Common Parallelization Strategies; Granularity; Load balancing; Examples: Parallel Search, Parallel Sorting, etc. Shared memory programming: threads, pthreads, locks and semaphores, Distributed-Memory Programming: Message Passing, MPI, PVM. Other Parallel Programming Systems, Distributed shared memory, Aurora: Scoped behavior and abstract data types, Enterprise: Process templates. Research Topics.
Class TimeTuesdays and Thursdays 12:00 Noon - 1:30 PM
Texts
Our Primary Texts:
Nancy A. Lynch, Distributed Algorithms, Morgan Kauffman, San Francisco, 1996.
M. Goodrich and R. Tamassia, Algorithm Design, John Wiley and Sons, Inc., 2002.
Selim G. Akl, Parallel Computation: Models and Methods, Prentice Hall, New Jersey, 1996.
Our Secondary Text:
Gerald Tel, Introduction to Distributed Algorithms, Cambridge University Press, New York, 1994.
HEC Recommended Text Books/Reference Books:B. Wilkinson and M. Allen, Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, Prentice Hall, 1999.
W. Stevens, Advanced Programming in the Unix Environment, Addison-Wesley, 1993.
EthicsThe Honor Code will be strictly enforced in the classroom. It is a violation to represent joint work as your own or to let others use your work; always acknowledge any assistance you received in preparing work that bears your name. You are expected to work independently unless explicitly permitted to collaborate on a particular assignment. It is not a violation to discuss approaches to problems with others; however, it is a violation to use wording or expressions in your assignments that have been written by others without acknowledging the source.
Tentative Schedule
| Instr. | Topics | Class Strength | |
| 1. | Feb. 08 | Course Introduction | 34 |
| 2. | Feb. 10 | Introduction: Distributed/Network Algorithms/Computing | 35 |
| 3. | Feb. 15 | Computational Models for Distributed Computing | 43 |
| 4. | Feb. 17 | Leader Algorithm (Synchronous) | 35 |
| 5. | Feb. 22 | Leader Algorithm (Asynchronous), Complexities, Correctness, etc. | 42 |
| 6. | Feb. 24 | Leader Tree Algorithm (Synchronous) | 56 |
| 7. | Mar. 01 | Performance of Tree Leader Algorithms | 44 |
| 8. | Mar. 03 | Breadth-First Search Alg. (Synchronous) | 27 +3 = 30 |
| 9. | Mar. 08 | Breadth-First Search Alg. (Asynchronous) | 37 |
| 10. | Mar. 10 | Baruvka's MST Algorithm (Sequential and in Distributed setting) | 37 |
| 11. | Mar. 15 | Flooding Algorithms (Hop count & Sequence Number) | 35 |
| 12. | Mar. 17 | Bellman and Ford Algorithm (Unicast Routing) | 32 |
| 13. | Mar. 22 | Link-State Algorithm
(Unicast Routing) |
36 |
| 14. | Mar. 24 | Reverse Path Forwarding Algorithm (Multicast Routing) | 36 |
| 15. | Mar. 29 | Pruning and Performance of RPF Algorithm | 33 |
| 16. | Mar. 31 | Center-Based Algorithm (Multicast Routing) | 15 |
| 17. | Apr. 05 | Revision | |
| 18. | Apr. 07 | Midterm | |
| 19. | Apr. 12 | Parallel Algorithms/Computing Introduction | 8 |
| 20. | Apr. 14 | Parallel Models of Computation | 33 |
| 21. | Apr. 19 | Analyzing Parallel Algorithms | 5 |
| 22. | Apr. 21 | Introduction Parallel Search | 3 |
| 23. | Apr. 26 | Sequential and Binary Searches (Revision) | 41 |
| 24. | Apr. 28 | Broadcasting a Data on EREW SM SIMD Computer | 34 |
| 25. | May 03 | No Class Unscheduled Faculty Meeting |
1 |
| 26. | May 05 | Prefix Sum Computation | 37 + 3 = 40 |
| 27. | May 10 | EREW Searching | 39 |
| 28. | May 12 | Parallel Searching ???? | 37 |
| 29. | May 17 | No Class (Classroom Repair) | 36 |
| 30. | May 19 | Searching on a Tree | 38 |
| 31. | May 24 | Parallel Searching | 37 |
| 32. | May 26 | Midterm Review | 32 |
| 33. | May 31 | CREW Searching | |
| 34. | June 02 | Searching on SM SIMD Computer | |
| 35. | June 07 | Final Exam |
Instructions/Lectures
Exams| Midterm | April 7, 2011 | 12:00 - 1:30 PM |
| Final | June 7, 2011 | Evening Session |
Points Distribution|
Quizzes/Class Participation |
10% |
| Midterm | 30% |
| Final | 60% |
Grades
| A+ | 0 |
| A | 10 |
| B+ | 1 |
| B | 5 |
| C+ | 3 |
| C | 4 |
| D+ | 1 |
| D | 2 |
| F | 18 |
You can do it if you try!
If you wish to succeed in this course