  Given a directed graph $G$ and integers $k$ and $l$, a D-core is the maximal
subgraph $H \subseteq G$ such that for every vertex of $H$, its in-degree and
out-degree are no smaller than $k$ and $l$, respectively. For a directed graph
$G$, the problem of D-core decomposition aims to compute the non-empty D-cores
for all possible values of $k$ and $l$. In the literature, several
\emph{peeling-based} algorithms have been proposed to handle D-core
decomposition. However, the peeling-based algorithms that work in a sequential
fashion and require global graph information during processing are mainly
designed for \emph{centralized} settings, which cannot handle large-scale
graphs efficiently in distributed settings. Motivated by this, we study the
\emph{distributed} D-core decomposition problem in this paper. We start by
defining a concept called \emph{anchored coreness}, based on which we propose a
new H-index-based algorithm for distributed D-core decomposition. Furthermore,
we devise a novel concept, namely \emph{skyline coreness}, and show that the
D-core decomposition problem is equivalent to the computation of skyline
corenesses for all vertices. We design an efficient D-index to compute the
skyline corenesses distributedly. We implement the proposed algorithms under
both vertex-centric and block-centric distributed graph processing frameworks.
Moreover, we theoretically analyze the algorithm and message complexities.
Extensive experiments on large real-world graphs with billions of edges
demonstrate the efficiency of the proposed algorithms in terms of both the
running time and communication overhead.
