Stateless protocols are advantageous in high volume applications, increasing performance by removing the load caused by retention of session information and by providing crash tolerance. In this paper we present an optimal stateless information dissemination algorithm for synchronous distributed systems. The termination time is considerable lower than that of a recently proposed stateless dissemination protocol. Apart from a special case the new algorithm achieves the minimum possible termination time. The problem of selecting k dissemination nodes with minimal termination time is NP-hard. We prove that unless NP = P there is no approximation algorithm for this problem with approximation ratio 3/2-ε. We also prove for asynchronous systems that deterministic stateless information dissemination is only possible if a large enough part of the message can be updated by each node.