PSP stands for Programs, Specifications and Proofs. The emphasis of the work of our group is to derive parallel and distributed programs in a rigorous manner. The group is supervised by Jayadev Misra , who developed the theories we work on. Powerlists Powerlists is a notation for describing synchronous parallel programs and circuits. The data structure is a list of length equal to a power of two, with two different operations for balanced divisions of lists.
Many parallel algorithms have a succinct presentation and simple proofs in the powerlist notation.
A Structure for Parallel Recursion presents the notation and gives numerous examples of algorithms and proofs of their correctness, including the Fast Fourier Transform and Batcher's sorting network. Will Adams has studied how different arithmetic circuits, such as adders and multipliers, can be specified and proved correct in the powerlist notation. His paper Verifying adder circuits using powerlists is available. Jacob Kornerup has studied how powerlist programs can be mapped efficiently to different parallel architectures, specially hypercubes. See his List of papers for details about this research.