Our main contributions are: (a) A necessary and sufficient condition for achieving RMT in the partial knowledge model with a general adversary, yielding a characterization of the minimal level of knowledge which renders the problem solvable in a certain network. In order to show the sufficiency of the condition, we propose the RMT-Partial Knowledge Algorithm (RMT-PKA), an algorithm that solves RMT whenever the condition is met. This implies that RMT-PKA achieves reliable message transmission in every instance where this is possible, therefore it is a unique algorithm . To the best of our knowledge, this is the first unique protocol for RMT against general adversaries in the partial knowledge model. (b) A study of efficiency in the case of the ad hoc network model: we show that either the Z-CPA protocol  is fully polynomial or no unique fully polynomial protocol for RMT exists, thus introducing a new notion of uniqueness with respect to efficiency that we call poly-time uniqueness.
To obtain our results we introduce, among others, a joint view operation on adversary structures, allowing participants to combine their local knowledge in a sound manner, a new notion of separator (RMT-cut), appropriate for RMT in unreliable networks, and a self-reducibility property of the RMT problem, which we show by means of a protocol composition. The latter plays a crucial role in proving the poly-time uniqueness of Z-CPA.Category / Keywords: reliable message transmission; byzantine adversary; general adversary; partial knowledge; ad hoc model Date: received 14 Mar 2015, last revised 23 May 2016 Contact author: sakaval at corelab ntua gr Available format(s): PDF | BibTeX Citation Note: Minor changes Version: 20160523:155207 (All versions of this report) Short URL: ia.cr/2015/243 Discussion forum: Show discussion | Start new discussion