Revocation in sensor networks is a challenging problem because asymmetric key cryptosystems are unsuitable for use in resource constrained sensor nodes. We present some properties of node revocation in distributed sensor networks (DSN) and explain their implementation challenges. We illustrate these challenges by analyzing prior work in centralized and distributed revocation schemes for DSNs. We present a distributed revocation scheme for DSNs based on voting, that provides revocation vote authenticity, improved resilience to node replication, and well- defined policies for revocation. We also present the correctness properties of our scheme and prove its robustness in the context of the various problems identified in distributed revocation. Further, we explain why tracking the degree of connectivity of sensor nodes in a DSN is a complex problem and identify its role in solving the distributed revocation problem.