Print

Parallel and Distributed Algorithms

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.