In this paper, we study the following randomized broadcasting protocol. At some time t an information r is placed at one of the nodes of a graph. In the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this neighbor by sending a copy of r to it. We begin by developing tight lower and upper bounds on the runtime of the algorithm described above. First, it is shown that on Δ-regular graphs this algorithm requires at least log2−1Δn+log(ΔΔ−1)Δn−o(logn)≈1.69log2n rounds to inform all n nodes. Together with a result of Pittel [B. Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, 47 (1) (1987) 213–223] this bound implies that the algorithm has the best performance on complete graphs among all regular graphs. For general graphs, we prove a slightly weaker lower bound of log2−1Δn+log4n−o(logn)≈1.5log2n, where Δ denotes the maximum degree of G. We also prove two general upper bounds, (1+o(1))nlnn and O(nΔδ), respectively, where δ denotes the minimum degree.The second part of this paper is devoted to the analysis of fault-tolerance. We show that if the informed nodes are allowed to fail in some step with probability 1−p, then the broadcasting time increases by at most a factor 6/p. As a by-product, we determine the performance of agent based broadcasting in certain graphs and obtain bounds for the runtime of randomized broadcasting on Cartesian products of graphs.