King, Valerie



Phone number: (250) 472-5727
Department: Computer Science

Research description:

-Algorithm design and analysis
-Theory of computing
-Distributed computing
-Graph algorithms and data structures
-Randomized algorithms and probabilistic analysis
-Concrete complexity
-Applications to computational biology and networks
Expertise Profile
Sometimes, computer networks act like soldiers in a war zone. Each computer--or soldier--has some action in mind, and each wants to agree on a single action. However, some soldiers may be traitors trying to prevent their success.

This is called "the Byzantine Agreement problem," and computer scientist Valerie King looks for fixes.

The Byzantine Agreement problem occurs in Distributed systems--software where computer networks communicate by passing messages. Even multiplayer online gaming software can face this problem. In distributed computing systems, Networks made up of hundreds of thousands of computers need to work together to solve a problem. Sometimes computers in the network engage in malicious behaviour, or they simply malfunction. They, like spies in a war, prevent the rest from reaching the correct solution.

Dr. King writes randomized algorithms, where the choice of instruction partially depends on information thought to be random, like atmospheric noise. Her algorithms allow computers to recognize the invading malware and malfunctioning machines, so that they can ignore the information sent by the bad computers and continue to coordinate with the good ones. "If it becomes practical to do this, even malware could see everything we send each other, and they still wouldn't be able to prevent us from co-ordinating."

Dr. King wants students to understand and participate in her work. She often hires undergraduate students to participate in research. "Those undergraduate experiences lead people to graduate schools," she says. "It really is a good experience for people."

< Browse all experts