ACE Seminar: Reliable Message Transmission Despite Limited Knowledge and Powerful Adversaries

Speaker: Professor Aris Pagourtzis

Date/Time: 12-May-2016, 16:00 UTC





A fundamental primitive in distributed computing is Reliable Message Transmission (RMT), which refers to the task of correctly sending a message from a party to another, despite the presence of Byzantine corruptions. In this work we address the problem in the general adversary model of Hirt and Maurer, which subsumes earlier models such as the global or local threshold adversaries. Regarding the topology knowledge, we introduce and discuss the Partial Knowledge Model, which encompasses both the full knowledge and the ad hoc model; the latter assumes knowledge of the local neighborhood only.


Our main contributions are: (a) A necessary and sufficient condition for achieving RMT in the partial knowledge model with a general adversary; in order to show sufficiency, we propose RMT-PKA, a protocol that solves RMT whenever this is possible, therefore it is a so called 'unique' protocol. 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 recently proposed 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 employ, among others, a novel 'joint view' operation on adversary structures, 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.


Based on joint work with Giorgos Panagiotakos and Dimitris Sakavalas

Online paper:


Personal Website:

This page was last modified on 27 Mar 2014.