Simultaneous computation by multiple processing units is a fundamental concept in modern computing. The number of processing units may vary from two to several thousand. The action of individual units may be centrally coordinated (parallel computation), or autonomous (distributed computation). Parallel algorithms have numerous applications in computational science and processing of massive datasets on parallel computers, processor clusters and multicore processors. Distributed algorithms form the basis of modern networking technologies and the internet.

DIMAP members have contributed to research on parallel and distributed algorithms for several decades. These contributions include efficient parallel algorithms for a variety of combinatorial, matrix and string problems; new important techniques for network routing and network design; studies on limits of parallel and distributed computation in various contexts.

A common theme of the current research of DIMAP in this area is the analysis of resource limitations inherent in parallel and distributed algorithms, and the design of efficient techniques for optimising the use of limited resources. Depending on a particular application, the resources in question may include processing power, communication bandwidth, synchronisation frequency, or network congestion. We aim at developing models and techniques that capture the essential features of modern computers and networks, and provide solutions that are both efficient and widely applicable.

Sample publications:

• P. Krusche and A. Tiskin. Computing alignment plots efficiently. In Proceedings of ParCo, 2009, to appear.
• P. Krusche and A. Tiskin. String comparison by transposition networks. In Proceedings of London Algorithmics Workshop, 2008. Appeared in London Algorithmics 2008: Theory and Practice, vol. 11 of Texts in Algorithmics, College Publications, pp. 184—204, 2009.
• H. Räcke. Optimal Hierarchical Decompositions for Congestion Minimization in Networks. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08), pages 255 - 264, 2008. Co-Winner of the STOC'2008 Best Paper Award.
• P. Krusche and A. Tiskin. Efficient parallel string comparison. In Proceedings of ParCo, vol. 38 of NIC Series, John von Neumann Institute for Computing, pages 193 - 200, 2007.
• A. Tiskin. Communication-efficient parallel generic pairwise elimination. Future Generation Computer Systems, 23(2): 179 - 188, 2007.
• A. Gupta, M. T. Hajiaghayi, and H. Räcke. Oblivious Network Design. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'06), pages 970 - 979, 2006.
• Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Räcke. Optimal oblivious routing in polynomial time. Journal of Computer and System Sciences, 69(3): 383 - 394, 2004.
• D. Irony, S. Toledo, and A. Tiskin. Communication lower bounds for distributed-memory matrix multiplication. Journal of Parallel and Distributed Computing, 64(9): 1017 - 1026, 2004.
• H. Räcke. Minimizing Congestion in General Networks. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), pages 43 - 52, 2002. Co-Winner of the FOCS'2002 Best Paper Award.
• M. Paterson, H. Schröder, O. Sýkora, and I. Vrto. Permutation Communication in All-Optical Rings. Parallel Processing Letters, 12(1): 23 - 29, 2002.
• A. Czumaj, F. Meyer auf der Heide, and V. Stemann. Contention Resolution in Hashing Based Shared Memory Simulations. SIAM Journal on Computing, 29(5): 1703 - 1739, March 2000.
• W. F. McColl and A. Tiskin. Memory-efficient matrix computations in the BSP model. Algorithmica, 24(3-4): 287 - 297, 1999.
• A. Tiskin. The bulk-synchronous parallel random access machine. Theoretical Computer Science, 196(1-2): 109 - 130, 1998.
• A. Czumaj, L. Gasieniec, M. Piotrow, and W. Rytter. Sequential and Parallel Approximation of Shortest Superstrings. Journal of Algorithms, 23(1): 74 - 100, 1997.
• A. Czumaj, Z. Galil, L. Gasieniec, K. Park, and W. Plandowski. Work-Time-Optimal Parallel Algorithms for String Problems. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC'95), pages 713 - 722, 1995.
• M. S. Paterson. Improved sorting networks with O(log N) depth. Algorithmica, 5(1-4): 75 - 92, 1990.
• A. C. Greenberg, R. E. Ladner, M. S. Paterson, and Z. Galil. Efficient parallel algorithms for linear recurrence computation. Information Processing Letters, 15(1): 31 - 35, 1982.
• I. Munro and M. Paterson. Optimal algorithms for parallel polynomial evaluation. Journal of Computer and System Sciences, 7(2): 189 - 198, 1973.