  Due to the unstructuredness and the lack of schemas of graphs, such as
knowledge graphs, social networks, and RDF graphs, keyword search for querying
such graphs has been proposed. As graphs have become voluminous, large-scale
distributed processing has attracted much interest from the database research
community. While there have been several distributed systems, distributed
querying techniques for keyword search are still limited. This paper proposes a
novel distributed keyword search system called $\DKWS$. First, we
\revise{present} a {\em monotonic} property with keyword search algorithms that
guarantees correct parallelization. Second, we present a keyword search
algorithm as monotonic backward and forward search phases. Moreover, we propose
new tight bounds for pruning nodes being searched. Third, we propose a {\em
notify-push} paradigm and $\PINE$ {\em programming model} of $\DKWS$. The
notify-push paradigm allows {\em asynchronously} exchanging the upper bounds of
matches across the workers and the coordinator in $\DKWS$. The $\PINE$
programming model naturally fits keyword search algorithms, as they have
distinguished phases, to allow {\em preemptive} searches to mitigate staleness
in a distributed system. Finally, we investigate the performance and
effectiveness of $\DKWS$ through experiments using real-world datasets. We find
that $\DKWS$ is up to two orders of magnitude faster than related techniques,
and its communication costs are $7.6$ times smaller than those of other
techniques.
