  Online streaming algorithms, tailored for continuous data processing, offer
substantial benefits but are often more intricate to design than their offline
counterparts. This paper introduces a novel approach for automatically
synthesizing online streaming algorithms from their offline versions. In
particular, we propose a novel methodology, based on the notion of relational
function signature (RFS), for deriving an online algorithm given its offline
version. Then, we propose a concrete synthesis algorithm that is an
instantiation of the proposed methodology. Our algorithm uses the RFS to
decompose the synthesis problem into a set of independent subtasks and uses a
combination of symbolic reasoning and search to solve each subproblem. We
implement the proposed technique in a new tool called Opera and evaluate it on
over 50 tasks spanning two domains: statistical computations and online
auctions. Our results show that Opera can automatically derive the online
version of the original algorithm for 98% of the tasks. Our experiments also
demonstrate that Opera significantly outperforms alternative approaches,
including adaptations of SyGuS solvers to this problem as well as two of
Opera's own ablations.
