Paper 2015/243

Reliable communication via semilattice properties of partial knowledge

Aris Pagourtzis, Giorgos Panagiotakos, and Dimitris Sakavalas

Abstract

A fundamental communication 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 [5], which subsumes earlier models such as the global or local threshold adversaries. Regarding the topology knowledge, we employ the recently introduced Partial Knowledge Model [12], which encompasses both the full knowledge and the ad hoc model; the latter assumes knowledge of the local neighborhood only. Our main contribution is a tight condition for achieving RMT in the partial knowledge model under a general adversary. A key algorithmic tool that we define and use is the joint view operation which imposes a semilattice structure on the partial knowledge possessed by different parties. In this context, we prove that the worst possible adversary structure, conforming with the initial knowledge of a set of parties, can be expressed as the supremum of the parties’ knowledge under the semilattice partial order. The new operation allows for the definition of an appropriate network separator notion that yields a necessary condition for achieving RMT. In order to show the sufficiency of the condition, we propose the RMT Partial Knowledge Algorithm (RMT-PKA), an algorithm that also employs the joint view operation to solve 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 [13]. To the best of our knowledge, this is the first unique protocol for RMT against general adversaries in the partial knowledge model. Due to the generality of the model, our results provide, for any level of topology knowledge and any adversary structure, an exact characterization of instances where RMT is possible and an algorithm to achieve RMT on such instances.

Note: Minor changes