Many signal processing algorithms break the target signal into overlapping segments (also called windows, or patches), process them separately, and then stitch them back into place to produce a unified output. At the overlaps, the final value of those samples that are estimated more than once needs to be decided in some way. Averaging, the simplest approach, often leads to unsatisfactory results. Significant work has been devoted to this issue in recent years. Several works explore the idea of a weighted average of the overlapped patches and/or pixels; others promote agreement (consensus) between the patches at their intersections. Agreement can be either encouraged or imposed as a hard constraint. This work develops on the latter case. The result is a variational signal processing framework, named PACO, which features a number of appealing theoretical and practical properties. The PACO framework consists of a variational formulation that fits a wide variety of problems, and a general ADMMbased algorithm for minimizing the resulting energies. As a byproduct, we show that the consensus step of the algorithm, which is the main bottleneck of similar methods, can be solved efficiently and easily for any arbitrary patch decomposition scheme. We demonstrate the flexibility and power of PACO on three different problems: image inpainting (which we have already covered in previous works), image denoising, and contrast enhancement, using different cost functions including Laplacian and Gaussian Mixture Models.