Maxwell Young

My research addresses problems in the areas of distributed computing, networks, and security. Generally, I'm interested in whether networks can be made robust to failures using protocols that consume minimal resources and still yield high performance. Addressing this topic often requires making use of probabilistic techniques, graph theory, and cryptography. Here are some topics that I've been working on lately.


Resource-Competitive Algorithms. A strong current interest is the design of algorithms whose cost is parameterized by the adversary's expenditure of a scarce resource. For example, in many wireless ad-hoc networks, energy is a scarce resource for both correct and adversarial devices, and the latter must expend energy to carry out attacks on the network, such as jamming the wireless communication channel. We would like to design algorithms with two properties. First, when there is no attack, correct devices can run the algorithm at low cost. Second, when there is an attack, the malicious devices drain their respective resources (i.e., onboard batteries) more rapidly than the correct devices. This gives us an adaptive defense that scales to quickly bankrupt an attacker, which then allows correct devices to succeed in their operations. The same strategy can be used in wired networks, where we can measure resources in terms of, say, communication complexity or computational power. Resource competitiveness puts an interesting spin on the design of attack-resistant distributed algorithms, and I've had fun working with my colleagues on this topic; here are a couple examples:


Contention-Resolution Algorithms. In many settings, such as standard WiFi (IEEE 802.11) or wireless ad-hoc networks, devices need to share access to a common communication channel. Without a central authority, coordinating access to the channel can be challenging. Energy constraints on the devices, along with interference (environmental or malicious) on the channel, adds to the complexity of designing algorithms for this task. Here are a couple samples of work I've coauthored in this area:


Secure and Scalable Algorithms for Overlay Networks. I'm interested in designing overlays that can tolerate malicious faults. For instance, distributed hash tables (DHTs) are a well-known construction allowing for scalable content storage and retrieval. I've worked on several results addressing the design of DHTs that tolerate malicious (or Byzantine) faults, while remaining scalable in terms of state and communication complexity. More recently, I've also become interested in defending against other attacks in permissionless systems. With my colleagues, I've looked into defenses that make careful use of resource-burning in order to provide provable security guarantees. A couple examples are the following: