Paper Info
Title
A Case for Stale Synchronous Distributed Model for Declarative Recursive Computation.
Abstract
A large class of traditional graph and data mining algorithms can be concisely expressed in Datalog, and other Logic-based languages, once aggregates are allowed in recursion. In fact, for most BigData algorithms, the difficult semantic issues raised by the use of non-monotonic aggregates in recursion are solved by Pre-Mappability (PreM), a property that assures that for a program with aggregates in recursion there is an equivalent aggregate-stratified program. In this paper we show that, by bringing together the formal abstract semantics of stratified programs with the efficient operational one of unstratified programs, PreM can also facilitate and improve their parallel execution. We prove that PreM-optimized lock-free and decomposable parallel semi-naive evaluations produce the same results as the single executor programs. Therefore, PreM can be assimilated into the data-parallel computation plans of different distributed systems, irrespective of whether these follow bulk synchronous parallel (BSP) or asynchronous computing models. In addition, we show that non-linear recursive queries can be evaluated using a hybrid stale synchronous parallel (SSP) model on distributed environments. After providing a formal correctness proof for the recursive query evaluation with PreM under this relaxed synchronization model, we present experimental evidence of its benefits.
Year
DOI
Venue
2019
10.1017/S1471068419000358
THEORY AND PRACTICE OF LOGIC PROGRAMMING
Keywords
Field
DocType
Datalog,Deductive Databases,Recursive Query,Stale Synchronous Parallel Model,Bulk Synchronous Parallel Model,Parallel and Distributed Computing
Distributed element model,Computer science,Theoretical computer science,Recursive computation
Journal
Volume
Issue
ISSN
19
SP5-6
1471-0684
Citations 
PageRank 
References 
1
0.35
0
Authors
2
Name
Order
Citations
PageRank
Ariyam Das1348.00
Carlo Zaniolo243051447.58