Communication vs Synchronisation in Parallel String Comparison
Alexander Tiskin · 2020
The longest common subsequence (LCS) problem is fundamental in computer science and its many applications. Parallel algorithms for this problems have been studied previously, in particular in the bulk-synchronous parallelism (BSP) model, which treats local computation, communication and synchronisation as independent scarce resources of a computing system. We consider primarily BSP algorithms running in either constant or polylogarithmic synchronisation. Based on our previous results on the algebraic structure and efficient algorithms for semi-local LCS, we present BSP algorithms for parallel semi-local LCS, improving on the existing upper bounds on communication and synchronisation; in particular we present the first constant-sync work-optimal LCS algorithm.