Course Instructor: Valentin Cristea, Ciprian Dobre

The course objectives are: to learn parallel and distributed algorithms development techniques for shared memory and message passing models; to study the main classes of parallel algorithms; to study the complexity and correctness models for parallel algorithms. More specific: Learning the conceptual models for the specification and verification of parallel and distributed algorithms (P&D); Understanding the complexity models of P&D algorithms; Learning the development methods of efficient P&D algorithms using data partitioning and functional partitioning, parallelism exploitation for different process topologies, hiding communication latencies, load balancing; Development techniques for parallel algorithms; examples from the main classes: prefix algorithms, search, sort, selection, matrix processing, graph algorithms, lists, trees; Study of the main development techniques of classes of distributed algorithms: wave algorithms, mutual exclusion, topology establishment, termination, fault tolerance, leader election, genetic algorithms;

Syllabus:

• Categories of applications.
• Conceptual models.
• Programming methods.
• Parallel and distributed systems.
• A language for algorithms presentation.
• Concurrency and synchronization.
• Atomicity.
• Barriers.
• Data parallelism.
• Prefix algorithms.
• Processing lists and matrices.
• Message passing.
• Complexity of P&D algorithms Performance metrics.
• Complexity models: Work-depth, Foster, LogP.
• Algorithms development using shared variables.
• Languages for concurrent programming.
• Concurrent access to priority queues.
• Algorithms development for PRAM models.
• Parallel search.
• Parallel selection.
• Algorithm development using message passing.
• Languages and libraries for distributed programming.
• Logical clocks and ordering of events.
• Vector timestamps.
• Topology establishment.
• Heartbeat algorithm.
• Probe-echo messages.
• Termination of distributed programs.
• Termination detection in ring and graph topologies.
• Termination detection using message echoes: Dijkstra-Scholten.
• Detecting termination using mark messages.
• Huang algorithm.
• Algorithms for fault tolerant systems.
• Byzantine generals' problem.
• Solution with oral messages.
• Solution with signed messages.
• Wave algorithms and leader election.
• Ring, tree, echo, and phase algorithms.
• Finn's algorithm.
• Leader election with wave algorithms.
• LeLann, Lelann-Chang-Robert, and Hirschberg-Sinclair algorithms.
• Parallel genetic algorithms.
• Model, rationale, implementation.
• Transport problem.
• Parallel genetic algorithms.
• Distributed algorithms for mutual exclusion.
• Classification, complexity metrics. Lamport, Ricart-Agarwala, Roucairol-Carvalho, Maekawa, Suzuki Kasami, and Raymond algorithms.