Is it possible that a signing algorithm produces no output? I am reading Vadim Lyubashevsky's paper on Lattice Signatures without Trapdoors and I came across a somehow counter-intuitive part where he defined an algorithm $\mathcal{A}$:


$y\leftarrow D_\sigma^m$, where $D_\sigma^m$ is the discrete Gaussian distribution centered at $0$ with standard deviation $\sigma$ on $\mathbb{Z}^m$.
$c$ is some hashed value
$z\leftarrow Sc+y$, where $S$ is the signing key.
output $(z,c)$ with some probability.


The pair $(z,c)$ is the potential signature and can only be output with the given probability in step $4$. He also mentioned that if nothing was output, the signer runs the signing algorithm again until some signature is outputted.

I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output. It also seems to violate the definition of an algorithm by Knuth. Am I missing something here?

Thanks!
I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output.


Actually, step 1 is randomized; that is, it will select a value of $r$ randomly (from some probability distribution).  If step 4 decides to rerun the procedure, then step 1 will likely generate some different value, and so the output would be different.


  It also seems to violate the definition of an algorithm by Knuth. 


Well, by Knuth's definition, it's a "computational method" rather than "an algorithm".  I don't think, in this case, the distinction is important, as the algorithm will terminate with probability 1 (and terminate quickly with high probability).  I don't believe that Knuth had randomized procedures (like this one) in mind when he wrote his definitions...