Towards a formalization and generalization of divide-and-conquer parallel design pattern
Structuring is essential in parallel programming, as it helps manage the inherent complexity of concurrent computation. One effective way to achieve such structuring is through programming patterns and algorithmic skeletons. Among these, the divide-and-conquer pattern plays a fundamental role. It is defined by a recurrence relation that expresses the solution to a problem in terms of the solutions to smaller subproblems of the same nature. This pattern supports a wide range of computational scenarios, making it valuable to develop a general specification that captures all its possible forms and use cases. We aim to demonstrate that the divide-and-conquer pattern can be generalized in such a way that it subsumes many other parallel programming patterns. To support this claim, we propose a formal and comprehensive formulation of the divide-and-conquer paradigm. Such a generalization can serve not only theoretical purposes but also practical ones—particularly in the design of parallel programming libraries and APIs that rely on divide-and-conquer-based skeletons.