Distribution of service time when server restarts can occur (This is a differently formulated version of the question. There were no answers, comments or votes on the first version so I thought I'd give it another shot.)
Suppose a server processes jobs that take a random amount of time to process. Denote by $B$ the random variable service time. Suppose that B is exponentially distributed with parameter $\mu$, so $f_{B}(t) = \mu e^{-\mu t}$ and $P(B < t) = 1 - e^{-\mu t}$.
Now we want to consider the possibility that the server fails to process a job and has to start over. In particular, we consider the cases
(1) the breakdown occurs after a fixed amount of time;
(2) the breakdown occurs after a random amount of time, according to some probability density function.
Let $B'$ denote the time passed until the processing fails. Let $p$ be the probability that a job fails to be processed and thus causes the server to start over again. I want to know the distribution, in both cases, of the time it takes for a job to be processed.
I have made attempts at both cases but I'm not sure I'm going about it the right way. 
For the first case, suppose the server restarts $N$ times (a random amount). Then I'm interested in $P(NB' + B \leq t)$, which I could compute using the law of total probability, ie $$\begin{eqnarray*}P(NB' + B \leq t) &=& \sum_{k=1}^{\infty} P(NB' + B \leq t|N=k)P(\text{the service fails k times}) \\&=& \sum_{N=1}^{\infty} P(NB' + B \leq t|N=k)p^k \\&=& \sum_{k=1}^{\infty} P(B\leq t - kB')p^k\end{eqnarray*}$$ is this correct or is this nonsense?
As for the second case, I'd suppose that we have iid random variables $B'_1,B'_2,\ldots,B'_N$ which denote the length of time it takes to break down, so then I'd guess that we would want to know $$P(B +\sum_{i=1}^{N} B'_i \leq t) = \sum_{k=1}^{\infty}P(B+\sum_{i=1}^{k}B'_i \leq t|N=k)P(\text{the service fails k times})$$
BI have the feeling that this isn't what the answer should be. Any comments on my interpretation of the question and my suggested way of solving this problem is most appreciated.
 A: 
The whole processing time of a job is exponential with parameter $\mu$. 

The result is a (thinly disguised) version of the waiting time paradox. 
Here is a proof.
Let $T$ denote the whole processing time of a job and $N_t$ the number of breakdowns/restarts that occurred before a given nonnegative time $t$. 
For each nonnegative $n$, the event $[T\geqslant t,N_t=n]$ is realized if the first $n$ tries failed and led to a breakdown, and if nothing occurred between the time of the $n$th breakdown/restart and time $t$. 
The time of the $n$th restart is  $R_n=B'_1+\cdots+B'_n$, hence
$$
[T\geqslant t,N_t=n]=[B_1>B'_1,\ldots,B_n>B'_n,t\geqslant R_n,B'_{n+1}>t-R_n,B_{n+1}>t-R_n].
$$
Consider the sigma-algebra $\mathfrak{R}$ generated by the sequence $(B'_k)$, or, equivalently, by the sequence $(R_k)$. Using the fact that, for every $k\leqslant n$, $P(B_k>B'_k|\mathfrak{R})=\mathrm{e}^{-\mu B'_k}$, and the density of $B_{n+1}$, one gets
$$
\mathrm P(T\geqslant t,N_t=n|\mathfrak{R})=\mathrm{e}^{-\mu B'_1}\cdots\mathrm{e}^{-\mu B'_n}\cdot\mathrm{e}^{-\mu(t-R_n)}\cdot[R_n\leqslant t<R_n+B'_{n+1}],
$$
hence
$$
\mathrm P(T\geqslant t,N_t=n|\mathfrak{R})=\mathrm{e}^{-\mu t}\cdot[R_n\leqslant t<R_{n+1}].
$$
Summing over $n\geqslant0$, one gets 
$
\mathrm P(T\geqslant t|\mathfrak{R})=\mathrm{e}^{-\mu t}
$. This proves that $T$ is independent of $\mathfrak{R}$ and exponentially distributed with parameter $\mu$.
