Michael J. Fischer
Encyclopedia
Michael John Fischer is a computer scientist
who works in the fields of distributed computing
, parallel computing
, cryptography
, algorithm
s and data structure
s, and computational complexity
.
, USA. He received his BSc
degree in mathematics
from the University of Michigan
in 1963. Fischer did his MA
and PhD
studies in applied mathematics
at Harvard University
; he received his MA degree in 1965 and PhD in 1968. Fischer's PhD supervisor at Harvard was Sheila Greibach
.
After receiving his PhD, Fischer was an assistant professor of computer science at Carnegie-Mellon University in 1968–1969, an assistant professor of mathematics at Massachusetts Institute of Technology
(MIT) in 1969–1973, and an associate professor of electrical engineering
at MIT in 1973–1975. At MIT he supervised doctoral students who became prominent computer scientists, including David S. Johnson
, Frances Yao
, and Michael Hammer
.
In 1975, Fischer was nominated as a professor of computer science
at the University of Washington
. Since 1981, he has been a professor of computer science at Yale University
. Fischer served as the editor-in-chief of the Journal of the ACM
in 1982–1986. He was inducted as a Fellow of the Association for Computing Machinery
(ACM) in 1996.
received the PODC Influential-Paper Award in 2001. Their work showed that in an asynchronous distributed system, consensus is impossible if there is one processor that crashes. Jennifer Welch writes that “This result has had a monumental impact in distributed computing, both theory and practice. Systems designers were motivated to clarify their claims concerning under what circumstances the systems work.”
Fischer was the program chairman of the first Symposium on Principles of Distributed Computing
(PODC) in 1982; nowadays, PODC is the leading conference in the field. In 2003, the distributed computing community honoured Fischer's 60th birthday by organising a lecture series during the 22nd PODC, with Leslie Lamport
, Nancy Lynch, Albert R. Meyer
, and Rebecca Wright as speakers.
for computing prefix sum
s efficiently. They show how to construct a circuit that computes the prefix sums; in the circuit, each node performs an addition of two numbers. With their construction, one can choose a trade-off between the circuit depth and the number of nodes. However, the same circuit designs were already studied much earlier in Soviet mathematics.
and formal grammar
s. One of Fischer's most-cited works deals with string matching. Already during his years at Michigan, Fischer studied disjoint-set data structures together with Bernard Galler
.
. In 1985, Fischer and his student Josh Cohen Benaloh presented one of the first electronic voting schemes.
Other contributions related to cryptography include the study of key exchange
problems and a protocol for oblivious transfer
. In 1984, Fischer, Silvio Micali
, and Charles Rackoff
presented an improved version of Michael O. Rabin
's protocol for oblivious transfer.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
who works in the fields of distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
, parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
, cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s and data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s, and computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
.
Career
Fischer was born in 1942 in Ann Arbor, MichiganMichigan
Michigan is a U.S. state located in the Great Lakes Region of the United States of America. The name Michigan is the French form of the Ojibwa word mishigamaa, meaning "large water" or "large lake"....
, USA. He received his BSc
BSC
BSC is a three-letter abbreviation that may refer to:Science and technology* Bachelor of Science , an undergraduate degree* Base Station Controller, part of a mobile phone network; see: Base Station subsystem...
degree in mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
from the University of Michigan
University of Michigan
The University of Michigan is a public research university located in Ann Arbor, Michigan in the United States. It is the state's oldest university and the flagship campus of the University of Michigan...
in 1963. Fischer did his MA
Master of Arts (postgraduate)
A Master of Arts from the Latin Magister Artium, is a type of Master's degree awarded by universities in many countries. The M.A. is usually contrasted with the M.S. or M.Sc. degrees...
and PhD
PHD
PHD may refer to:*Ph.D., a doctorate of philosophy*Ph.D. , a 1980s British group*PHD finger, a protein sequence*PHD Mountain Software, an outdoor clothing and equipment company*PhD Docbook renderer, an XML renderer...
studies in applied mathematics
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
at Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
; he received his MA degree in 1965 and PhD in 1968. Fischer's PhD supervisor at Harvard was Sheila Greibach
Sheila Greibach
Sheila Adele Greibach is a researcher in formal languages, automata,compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles....
.
After receiving his PhD, Fischer was an assistant professor of computer science at Carnegie-Mellon University in 1968–1969, an assistant professor of mathematics at Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
(MIT) in 1969–1973, and an associate professor of electrical engineering
Electrical engineering
Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...
at MIT in 1973–1975. At MIT he supervised doctoral students who became prominent computer scientists, including David S. Johnson
David S. Johnson
David Stifler Johnson is a computer scientist specializing in algorithms and optimization. He is currently the head of the Algorithms and Optimization Department of AT&T Labs Research. He was awarded the 2010 Knuth Prize....
, Frances Yao
Frances Yao
Frances Foong Yao is professor and head of the department of computer science at the City University of Hong Kong.After receiving a B.S. in mathematics from National Taiwan University in 1969, Yao did her Ph.D. studies under the supervision of Michael J. Fischer at the Massachusetts Institute of...
, and Michael Hammer
Michael Hammer
Michael Martin Hammer was an American engineer, management author, and a former professor of computer science at the Massachusetts Institute of Technology , known as one of the founders of the management theory of Business process reengineering .- Biography:Hammer, the child of Holocaust...
.
In 1975, Fischer was nominated as a professor of computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at the University of Washington
University of Washington
University of Washington is a public research university, founded in 1861 in Seattle, Washington, United States. The UW is the largest university in the Northwest and the oldest public university on the West Coast. The university has three campuses, with its largest campus in the University...
. Since 1981, he has been a professor of computer science at Yale University
Yale University
Yale University is a private, Ivy League university located in New Haven, Connecticut, United States. Founded in 1701 in the Colony of Connecticut, the university is the third-oldest institution of higher education in the United States...
. Fischer served as the editor-in-chief of the Journal of the ACM
Journal of the ACM
The Journal of the ACM is the flagship scientific journal of the Association for Computing Machinery . It is peer-reviewed and covers computer science in general, especially theoretical aspects. Its current editor-in-chief is Victor Vianu, from University of California, San Diego.The journal has...
in 1982–1986. He was inducted as a Fellow of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
(ACM) in 1996.
Distributed computing
Fischer is famous for his contributions in the field of distributed computing. His 1985 work with Nancy A. Lynch and Michael S. Paterson on consensus problemsConsensus (computer science)
Consensus is a problem in distributed computing that encapsulates the task of group agreement in the presence of faults.In particular, any process in the group may fail at any time. Consensus is fundamental to core techniques in fault tolerance, such as state machine replication.- Problem...
received the PODC Influential-Paper Award in 2001. Their work showed that in an asynchronous distributed system, consensus is impossible if there is one processor that crashes. Jennifer Welch writes that “This result has had a monumental impact in distributed computing, both theory and practice. Systems designers were motivated to clarify their claims concerning under what circumstances the systems work.”
Fischer was the program chairman of the first Symposium on Principles of Distributed Computing
Symposium on Principles of Distributed Computing
The Symposium on Principles of Distributed Computing is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery ....
(PODC) in 1982; nowadays, PODC is the leading conference in the field. In 2003, the distributed computing community honoured Fischer's 60th birthday by organising a lecture series during the 22nd PODC, with Leslie Lamport
Leslie Lamport
Leslie Lamport is an American computer scientist. A graduate of the Bronx High School of Science, he received a B.S. in mathematics from the Massachusetts Institute of Technology in 1960, and M.A. and Ph.D. degrees in mathematics from Brandeis University, respectively in 1963 and 1972...
, Nancy Lynch, Albert R. Meyer
Albert R. Meyer
Albert Ronald da Silva Meyer is a professor of computer science at Massachusetts Institute of Technology . He has been a Fellow of the American Academy of Arts and Sciences since 1987, and he was inducted as a Fellow of the Association for Computing Machinery in 2000.Meyer's seminal works...
, and Rebecca Wright as speakers.
Parallel computing
In 1980, Fischer and Richard Ladner presented a parallel algorithmParallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
for computing prefix sum
Prefix sum
In computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....
s efficiently. They show how to construct a circuit that computes the prefix sums; in the circuit, each node performs an addition of two numbers. With their construction, one can choose a trade-off between the circuit depth and the number of nodes. However, the same circuit designs were already studied much earlier in Soviet mathematics.
Algorithms and computational complexity
Fischer has done multifaceted work in theoretical computer science in general. Fischer's early work, including his PhD thesis, focused on parsingParsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
and formal grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
s. One of Fischer's most-cited works deals with string matching. Already during his years at Michigan, Fischer studied disjoint-set data structures together with Bernard Galler
Bernard Galler
Bernard A. Galler was an American mathematician and computer scientist at the University of Michigan who was involved in the development of large-scale operating systems and computer languages including the MAD programming language and the Michigan Terminal System operating system.He attended the...
.
Cryptography
Fischer is one of the pioneers in electronic votingElectronic voting
Electronic voting is a term encompassing several different types of voting, embracing both electronic means of casting a vote and electronic means of counting votes....
. In 1985, Fischer and his student Josh Cohen Benaloh presented one of the first electronic voting schemes.
Other contributions related to cryptography include the study of key exchange
Key exchange
Key exchange is any method in cryptography by which cryptographic keys are exchanged between users, allowing use of a cryptographic algorithm....
problems and a protocol for oblivious transfer
Oblivious transfer
In cryptography, an oblivious transfer protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred....
. In 1984, Fischer, Silvio Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
, and Charles Rackoff
Charles Rackoff
Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, Rackoff attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar at INRIA in France.He currently works at the...
presented an improved version of Michael O. Rabin
Michael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...
's protocol for oblivious transfer.