Grant: Discovery Grants Program - Individual
University of Victoria
$29,000.00
Algorithms for large scale networks
FY 2012-13
Summary
Recent years have seen a rapid increase in the presence of large networks of diverse users. Such systems have the potential to speed up computation through vast parallelization and also to revolutionize how we as a society organize our data, economic activity and decision-making. With this promise comes an exposure to new threats in the form of increasingly sophisticated malware. As our dependence on large networks grows, so does our need to develop algorithms which are robust to powerful malicious adversaries.
A starting point is a fundamental problem of coordination in distributed computing, the problem of bringing processors to agreement on a bit (Byzantine agreement) and a simple model of users, good users that follow the protocol and bad users controlled by a malicious adversary. This problem was commonly thought to have a communication bottleneck requiring all-to-all communication, making it impractical to consider for large size networks. Recently, we broke through some conjectured bottlenecks in this area. The theoretical limits of what can be done still remain open and we hope to develop both practical tools and theoretical understanding of what is possible.
When we look at the network as a community of users with individual preferences, other interesting problems arise. Rather than ``good"" nodes, we may have factions of nodes that co-operate if they are friends or it is to their benefit. On the frontier of law and economics, we consider how nodes in a game can coordinate to improve their overall benefit by voting to change the current rules of the game. We also ask how this and other coordination problems such as the decentralized scheduling of health care, may be done without losing privacy. While these problems have been studied by others, we will seek to implement them efficiently in large networks, without all-to-all communication.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
121617-2011
Name nom
King, Valerie
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2011
Award amount
29000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Algorithms for large scale networks
Keyword
NSERC
Application summary
Recent years have seen a rapid increase in the presence of large networks of diverse users. Such systems have the potential to speed up computation through vast parallelization and also to revolutionize how we as a society organize our data, economic activity and decision-making. With this promise comes an exposure to new threats in the form of increasingly sophisticated malware. As our dependence on large networks grows, so does our need to develop algorithms which are robust to powerful malicious adversaries.
A starting point is a fundamental problem of coordination in distributed computing, the problem of bringing processors to agreement on a bit (Byzantine agreement) and a simple model of users, good users that follow the protocol and bad users controlled by a malicious adversary. This problem was commonly thought to have a communication bottleneck requiring all-to-all communication, making it impractical to consider for large size networks. Recently, we broke through some conjectured bottlenecks in this area. The theoretical limits of what can be done still remain open and we hope to develop both practical tools and theoretical understanding of what is possible.
When we look at the network as a community of users with individual preferences, other interesting problems arise. Rather than ``good"" nodes, we may have factions of nodes that co-operate if they are friends or it is to their benefit. On the frontier of law and economics, we consider how nodes in a game can coordinate to improve their overall benefit by voting to change the current rules of the game. We also ask how this and other coordination problems such as the decentralized scheduling of health care, may be done without losing privacy. While these problems have been studied by others, we will seek to implement them efficiently in large networks, without all-to-all communication.