Newtonpedia ES
Home › Computing › Randal Bryant
Randal Bryant
Image: Wikimedia Commons

Randal Bryant

American computer scientist known for formal verification of digital hardware and software · 1952

Born
October 27, 1952
Country
United States
Section
Computing

Biography

Randal E. Bryant is an American computer scientist known for his work on formal verification, the mathematical checking that a chip or a program does what it should before it is manufactured or released. His research, developed mainly from the late 1980s onward, helped engineers prove the correctness of designs in an industry where a single error can be extremely expensive.

He was born on 27 October 1952 and grew up in Birmingham, Michigan. His grandfather, William Littell Everitt, led the electrical engineering department at the University of Illinois at Urbana-Champaign from 1949 to 1968. Bryant studied at the University of Michigan from 1970, earning a bachelor's degree in applied mathematics in 1973. His master's thesis, published in 1977, dealt with simulating packet communication systems and is regarded as one of the first publications on distributed simulation, the technique of splitting a computation across several machines. He completed his PhD in 1981 at the Massachusetts Institute of Technology, in the department of electrical engineering and computer science.

That same year he became an assistant professor at the California Institute of Technology, where he worked on VLSI circuit models (designs for chips containing thousands of transistors), logic simulation and chip testing. In 1984 he joined Carnegie Mellon University, where he would spend the rest of his academic career. From 1990 to 1991 he was a visiting research fellow at Fujitsu Laboratories.

His breakthrough came in 1986 with the paper «Graph-Based Algorithms for Boolean Function Manipulation». In it he introduced ordered binary decision diagrams (BDDs), a data structure that stores logical functions, the true-or-false rules that govern circuits, in a compact form that computers can manipulate quickly. BDDs became widely used in digital circuit testing and synthesis and in artificial intelligence planning. In 1992 he published a tutorial and update on the subject. The 1986 paper has the highest citation count of any publication in the Citeseer database of computer science literature.

In 1995 he published a method called symbolic trajectory evaluation for verifying systems, which industry adopted and which, according to available accounts, has been used notably at Intel. From 2004 he also promoted new research on data-intensive computing.

With David R. O'Hallaron he wrote Computer Systems: A Programmer's Perspective, a book that teaches how hardware, operating systems, compilers and networks shape a program's behaviour and performance, rather than focusing on how those systems are designed. The two teach the course 15-213 at Carnegie Mellon. The book, now in its third edition, has been translated into several languages and is used by universities around the world.

Bryant served as dean of Carnegie Mellon's School of Computer Science from 2004 to 2014, a period in which the school's combined enrollment rose by more than 50 percent. In 2014 and 2015 he worked at the White House Office of Science and Technology Policy as assistant director for information technology research and development, covering robotics, machine learning, high-performance computing and cloud computing. He retired in 2020 as a professor emeritus.

His legacy is also measured in recognition. He has been a member of the US National Academy of Engineering since 2003, received the ACM Kanellakis Theory and Practice Award in 1998 alongside Edmund Clarke, Ken McMillan and Allen Emerson, and was given the Phil Kaufman Award in 2009 for his advances in formal verification. His ideas remain part of chip design, where formal verification helps catch errors before production.

Main contributions

  • 1977Master's thesis on simulating packet communication systems, one of the first works on distributed simulation.
  • 1986Binary decision diagrams (BDDs), a compact data structure for manipulating logical functions by computer.
  • 1992A tutorial and update on binary decision diagrams.
  • 1995A method of symbolic trajectory evaluation for verifying digital systems, adopted by industry.
  • The textbook Computer Systems: A Programmer's Perspective, written with David R. O'Hallaron to teach how systems affect programs.

Teachers and students

Studied under:

Taught:

Sanjit SeshiaYirng-An ChenDerek Lee BeattyManish PandeyLawrence Peter HuangRune Møller Jensen

See their academic family tree →

Trivia and anecdotes

Knuth's praise

According to computer scientist Donald Knuth, BDDs are one of the only truly fundamental data structures to emerge in the previous twenty-five years.

The most-cited paper

The 1986 BDD paper has the highest citation count in the Citeseer database of computer science literature.

A family of artists

His sister, Lois Bryant, is a textile artist.

Their contemporaries

While Randal Bryant was alive (1952–)…

Alive at the same time

Discovered or invented in those years

  • 1957
    Artificial satelliteAn artificial satellite is a human-made object placed in orbit around a celestial body, usually Earth, to collect information, relay signals, or carry out a specific task.
  • 1969
    InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
  • 1971
    EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
  • 1973
    Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
  • 1989
    World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.
  • 1990
    Web browserA program that lets people access the web by fetching a page's files from a server and displaying them on screen as an interactive page.

See this life on the timeline →

More people in Computing