Attack-Resistant Algorithms for Massive Networks

Опубликовано 7 сентября 2016, 16:23

In this talk, we will describe new attack-resistant algorithms for peer-to-peer networks.  Our attack model is rather strong in that we assume that an omniscient and computationally unbounded adversary takes over up to a constant fraction of the peers in the network.  Our algorithms are scalable in the sense that for every peer, all major resource costs (e.g. latency, number of bits sent and received, number of links to other peers) are polylogarithmic in the number of peers in the network.  We present attack-resistant algorithms for the problems of leader election, Byzantine agreement and voting and describe a general framework that can be used to design such algorithms for other types of problems.  We also describe many areas for future work. These results are joint with Valerie King (U. Victoria), Vishal Sanwalani(U. Waterloo) and Erik Vee (IBM Labs), and describe work previously published in the Symposium of Discrete Algorithms(SODA), and that will appear in Foundations of Computer Science (FOCS).