We present Brahms, an algorithm for sampling random nodes in a large dynamic system prone to Byzantine failures. Brahms stores small state (logarithmic in system size) at each node, and yet overcomes Byzantine failures of a linear portion of the system. Brahms is composed of two sub-protocols. The first is a Byzantine-resistant gossip-based membership protocol. We prove that an adversary can bias the views maintained by this protocol, but under certain conditions, cannot poison the entire view with faulty node ids. We theoretically analyze the precise extent of the damage an adversary can cause such a protocol, and validate this using extensive simulations. The second subprotocol uses a novel data stream samplin approach to unbias the views of the former and creates random mebership samples; the data stream sampling mechanism constitutes an independent contribution. We prove that each node's sample converges to a near-uniform one over time. To our knowledge, no such property was proven for gossip-based membership in the past. Our thorough analysis quantifies the effectiveness of various Byzantine-resistance measures for gossip-based membership. The simulations shed additional light on the dynamics of the system. Theis talk is based on joint work with Edward Bortnikov Maxim Gurevich, Gabriel Kliot, and Alexander Shraer.