Tuple Space based Mobile Middleware (TSMM) intends to facilitate coordination of different components (i.e. agents) of supported applications in multiple mobile, unreliable networks, which is a challenging problem. This paper proposes TSMM-specific discovery and communication mechanisms that enable TSMM to provide coordination over multiple networks. The paper also presents an approach of formalizing proposed mechanisms using Mobile UNITY. © 2012 IEEE.