On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary
B. V. Ashwinkumar, Arpita Patra, Ashish Choudhary, Kannan Srinathan, Chandrasekharan Pandu Rangan · 2008
In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous network, tolerating a mixed adversary A(tb,tf), who has unbounded computing power and can corrupt tb and tf nodes in the network in Byzantine and fail-stop fashion respectively.