In this paper, we discuss the possibility of achieving on- chip fault-tolerant communication based on a new communication paradigm called stochastic communication.Specifically, for a generic tile-based architecture, we present a randomized algorithm which not only separates computation from communication, but also provides the required fault-tolerance to on-chip failures.This new technique is easy and cheap to implement in SoCs that integrate a large number of communicating IP cores.