image: Yossi Azar, Tel Aviv University; Andrei Broder, Google Research; Anna Karlin, University of Washington; Michael Mitzenmacher, Harvard University; and Eli Upfal, Brown University, receive the ACM Paris Kanellakis Theory and Practice Award for the discovery and analysis of balanced allocations, known as the power of two choices, and their extensive applications to practice. view more
Credit: Association for Computing Machinery
ACM, the Association for Computing Machinery, today announced the recipients of four prestigious technical awards. These leaders were selected by their peers for making contributions that extend the boundaries of research, advance industry, and lay the foundation for technologies that transform society.
Shyamnath Gollakota, University of Washington, is the recipient of the 2020 ACM Grace Murray Hopper Award for contributions to the use of wireless signals in creating novel applications, including battery-free communications, health monitoring, gesture recognition, and bio-based wireless sensing. His work has revolutionized and re-imagined what can be done using wireless systems and has a feel of technologies depicted in science fiction novels.
Gollakota defined the technology referred to today as ambient backscatter--a mechanism by which an unpowered, battery-less device can harvest existing wireless signals (such as broadcast TV or WiFi) in the environment for energy and use it to transmit encoded data. In addition, he has developed techniques that can use sonar signals from smartphones to support numerous healthcare applications. Examples include detection and diagnosis of breathing anomalies such as apnea, detection of ear infections, and even detection of life-threatening opioid overdoses. These innovations have the potential to transform the way healthcare systems will be designed and delivered in the future, and some of these efforts are now being commercialized for real-world use.
Gollakota also opened up a new field of extremely lightweight mobile sensors and controllers attached to insects, demonstrating how wireless technology can stream video data from the backs of tiny insects. Some observers believe this could be a first step to creating an internet of biological things, in which insects are employed as delivery vehicles for mobile sensors.
The ACM Grace Murray Hopper Award is given to the outstanding young computer professional of the year, selected on the basis of a single recent major technical or service contribution. This award is accompanied by a prize of $35,000. The candidate must have been 35 years of age or less at the time the qualifying contribution was made. Financial support for this award is provided by Microsoft.
Margo Seltzer, University of British Columbia; Mike Olson, formerly of Cloudera; and Keith Bostic, MongoDB, receive the ACM Software System Award for Berkeley DB, which was an early exemplar of the NoSQL movement and pioneered the "dual-license" approach to software licensing.
Since 1991, Berkeley DB has been a pervasive force underlying the modern internet: It is a part of nearly every POSIX or POSIX-like system, as well as the GNU standard C library (glibc) and many higher-level scripting languages. Berkeley DB was the transactional key/value store for a range of first- and second-generation internet services, including account management, mail and identity servers, online trading platforms and many other software-as-a-service platforms.
As an open source package, Berkeley DB is an invaluable teaching tool, allowing students to see under the hood of a tool that they have grown familiar with by use. The code is clean, well structured, and well documented - it had to be as it was meant to be consumed and used by an unlimited number of software developers.
As originally created by Seltzer, Olson and Bostic, Berkeley DB was distributed as part of the University of California's Fourth Berkeley Software Distribution. Seltzer and Bostic subsequently founded Sleepycat Software in 1996 to continue development of Berkeley DB and provide commercial support. Olson joined in 1997, and for ten years, Berkeley DB was the de facto data store for major web infrastructure. As the first production quality, commercial key/value store, it helped launched the NoSQL movement; as the engine behind Amazon's Dynamo and the University of Michigan's SLAPD server, Berkeley DB helped move non-relational databases into the public eye.
Sleepycat Software pioneered the "dual-license" model of software licensing: use and redistribution in Open Source applications was always free, and companies could choose a commercial license for support or to distribute Berkeley DB as part of proprietary packages. This model pointed the way for a number of other open source companies, and this innovation has been widely adopted in open source communities. The open source Berkeley DB release includes all the features of the complete commercial version, and developers building prototypes with open source releases suffer no delay when transitioning to a proprietary product that embeds Berkeley DB
In summary, Berkeley DB has been one of the most useful, powerful, reliable, and long-lived software packages. The longevity of Berkeley DB's contribution is particularly impressive in an industry with frequent software system turnover.
The ACM Software System Award is presented to an institution or individual(s) recognized for developing a software system that has had a lasting influence, reflected in contributions to concepts, in commercial acceptance, or both. The Software System Award carries a prize of $35,000. Financial support for the Software System Award is provided by IBM.
Yossi Azar, Tel Aviv University; Andrei Broder, Google Research; Anna Karlin, University of Washington; Michael Mitzenmacher, Harvard University; and Eli Upfal, Brown University, receive the ACM Paris Kanellakis Theory and Practice Award for the discovery and analysis of balanced allocations, known as the power of two choices, and their extensive applications to practice.
Azar, Broder, Karlin, Mitzenmacher and Upfal introduced the Balanced Allocations framework, also known as the power of two choices paradigm, an elegant theoretical work that had a wide-spread practical impact.
When n balls are thrown into n bins chosen uniformly at random, it is known that with high probability, the maximum load on any bin is bounded by (lg n/lg lg n) (1+o(1)). Azar, Broder, Karlin, and Upfal (STOC 94) proved that adding a little bit of choice makes a big difference. When throwing each ball, instead of choosing one bin at random, choose two bins at random, and then place the ball in the bin with the lesser load. This minor change brings on an exponential improvement; now with high probability, the maximal load in any bin is bounded by (lg lg n/lg 2)+O(1).
In the same work, they have shown that, if each ball has d choices, then the maximum load drops with high probability to (ln ln n/ ln d)+O(1). These results were greatly extended by Mitzenmacher in his 1996 PhD dissertation, where he removed the sequential setting, and developed a framework for using the power of two choices in queuing systems.
Since bins and balls are the basic model for analyzing data structures, such as hashing or processes like load balancing of jobs in servers, it is not surprising that the power of two choices that requires only a local decision rather than global coordination has led to a wide range of practical applications. These include i-Google's web index, Akamai's overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm. There are many other software systems that use balanced allocations as an important ingredient.
The Balanced Allocations paper and the follow-up work on the power of two choices are elegant theoretical results, and their content had, and will surely continue to have, a demonstrable effect on the practice of computing.
The ACM Paris Kanellakis Theory and Practice Award honors specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing. This award is accompanied by a prize of $10,000 and is endowed by contributions from the Kanellakis family, with additional financial support provided by ACM's Special Interest Groups on Algorithms and Computation Theory (SIGACT), Design Automation (SIGDA), Management of Data (SIGMOD), and Programming Languages (SIGPLAN), the ACM SIG Projects Fund, and individual contributions.
Hector Levesque and Moshe Vardi receive the ACM - AAAI Allen Newell Award.
Hector Levesque, University of Toronto, is recognized for fundamental contributions to knowledge representation and reasoning, and their broader influence within theoretical computer science, databases, robotics, and the study of Boolean satisfiability.
Levesque is recognized for his outstanding contributions to the broad core of logic-inspired Artificial Intelligence and the impact they have had across multiple sub-disciplines within computer science. With collaborators, he has made fundamental contributions to cognitive robotics, multi-agent systems, theoretical computer science, and database systems, as well as in philosophy and cognitive psychology.
These have inspired applications such as the semantic web and automated verification. He is internationally recognized as one of the deepest and most original thinkers within AI and a researcher who has advanced the flame that AI pioneer Alan Newell lit.
On the representation side, Levesque has worked on the formalization of several concepts pertaining to artificial and natural agents including belief, goals, intentions, ability, and the interaction between knowledge, perception and action.
On the reasoning side, his research has focused on how automated reasoning can be kept computationally tractable, including the use of greedy local search methods. He is recognized for his fundamental contributions to the development of several new fields of research including the fields of description logic, the study of tractability in knowledge representation, the study of intention and teamwork, the hardness of satisfiability problems, and cognitive robotics. Levesque has also made fundamental contributions to the development of the systematic use of beliefs, desires, and intentions in the development of intelligent software, where his formalization of many aspects of intention and teamwork has shaped the entire approach to the use of these terms and the design of intelligent agents.
Moshe Vardi, Rice University, is cited for contributions to the development of logic as a unifying foundational framework and a tool for modeling computational systems.
Vardi has made major contributions to a wide variety of fields, including database theory, program verification, finite-model theory, reasoning about knowledge, and constraint satisfaction. He is perhaps the most influential researcher working at the interface of logic and computer science, building bridges between communities in computer science and beyond. With his collaborators he has made fundamental contributions to major research areas, including: 1) investigation of the logical theory of databases, where his focus on the trade-off between expressiveness and computational complexity laid the foundations for work on integrity constraints, complexity of query evaluation, incomplete information, database updates, and logic programming in databases; 2) the automata-theoretic approach to reactive systems, which laid mathematical foundations for verifying that a program meets its specifications, and 3) reasoning about knowledge through his development of epistemic logic.
In database theory, Vardi developed a theory of general data dependencies, finding axiomatizations and resolving their decision problem; introduced two basic notions of measuring the complexity of algorithms for evaluating queries, data-complexity, and query-complexity, which soon became standard in the field; created a logical theory of data updates; and characterized the expressive power of query languages and related them to complexity classes.
In software and hardware verification, Vardi introduced an automata-theoretic approach to the verification of reactive systems that revolutionized the field, using automata on infinite strings and trees to represent both the system being analyzed and undesirable computations of the system. Vardi's automata-theoretic approach has played a central role over the last 30 years of research in the field and in the development of verification tools.
In knowledge theory, Vardi developed rigorous foundations for reasoning about the knowledge of multi-agent and distributed systems, a problem of central importance in many disciplines. His co-authored book on the subject is the definitive source for this field.
The ACM - AAAI Allen Newell Award is presented to an individual selected for career contributions that have breadth within computer science, or that bridge computer science and other disciplines. The Newell award is accompanied by a prize of $10,000, provided by ACM and the Association for the Advancement of Artificial Intelligence (AAAI), and by individual contributions.
###
About ACM
ACM, the Association for Computing Machinery, is the world's largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field's challenges. ACM strengthens the computing profession's collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.