  We introduce a method to construct non-Markovian variants of completely
positive (CP) dynamical maps, particularly, qubit Pauli channels. We identify
non-Markovianity with the breakdown in CP-divisibility of the map, i.e.,
appearance of a not-completely-positive (NCP) intermediate map. In particular,
we consider the case of non-Markovian dephasing in detail. The eigenvalues of
the Choi matrix of the intermediate map crossover at a point which corresponds
to a singularity in the canonical decoherence rate of the corresponding master
equation, and thus to a momentary non-invertibility of the map. Thereafter, the
rate becomes negative, indicating non-Markovianity. We quantify the
non-Markovianity by two methods, one based on CP-divisibility (Hall et al., PRA
89, 042120, 2014), which doesn't require optimization but requires
normalization to handle the singularity, and another method, based on
distinguishability (Breuer et al. PRL 103, 210401, 2009), which requires
optimization but is insensitive to the singularity.
