2019 Recipients of C&C Prize
Group B
Dr. Leslie Lamport
Distinguished Scientist, Microsoft Research
Citation
For outstanding contributions to the development of fundamental theories in distributed computing systems
Achievements
The architecture of super-distributed computing systems has been developing at a rapid pace. Early centralized computing systems went into full-scale operation in the 1960s and performed data processing in a central location. In the era of distributed computing, the system consisted of a network of a mainframe and minicomputers that evolved along with processing capabilities. In the 21st century, the omnipresence of the internet and the emergence of massive data centers have triggered rapid advances in cloud computing. The spread of IoT to everyday objects has further accelerated the paradigm shift to super-distributed computing. Today’s computing systems integrate a multitude of super-distributed devices into the processing system to focus on ensuring real-time responses in real-world control systems (e.g., self-driving vehicles). This requires a stable and highly autonomous environment.
Throughout his many years researching distributed computing systems, Dr. Leslie Lamport has provided a mathematical basis for computational processing environments and has presented a family of algorithms that facilitate data synchronization, which can pose problems for distributed systems in particular. Synchronization in a distributed processing system is based on the procedures and measures that coordinate the actions of processes. These procedures and measures have been applied to a vast range of familiar fields, such as multiprocessing systems, databases, and fault tolerance. The consensus algorithm in fault tolerance has contributed significantly to the development of these fields and is recognized as the starting point for the basic concept behind blockchains, a system of records of cryptocurrency transactions (i.e., network payments).
Dr. Lamport is best known for the following: 1) introduction of logical time and event ordering, 2) "Byzantine Failure" and the "Byzantine Generals problem" , which have been applied to blockchains, 3) sequential consistency in a shared-memory multiprocessor, 4) mutual exclusion algorithms (including the "bakery algorithm"), and 5) the temporal logic of actions . The common underlying idea behind the algorithms is that, in a distributed processing system with no physical clock, an appropriate number is assigned and judgment criteria (consensus is formed as a result) for each process is defined for events such as sending and receiving messages. Partial ordering that results in ambiguities is converted to total ordering, and a solution is provided that prevents contradictions from arising in the execution of processes within the entire system.
Amongst the work mentioned above, 1) “Lamport’s logical clock” has widespread applications, including synchronized processing in multiple processors and maintaining and controlling consistency in a distributed database. Because it is difficult to guarantee that physical clocks run in sync, focus turned to ordering critical events in a real system, which led to the concept of “Lamport’s logical clock.” In 1978, Dr. Lamport released one of his most influential papers, “Time, clocks, and the ordering of events in a distributed system,” which had over 11,000 citations at the time of writing. His presentation of the reliability problem in distributed systems indicated in 2) above—in other words, the concept of consensus-building conditions in a system with Byzantine fault tolerance—was applied to the blockchain-based Bitcoin (a type of cryptocurrency) that rapidly rose in popularity in the latter 2010s. Specifically, in the Byzantine generals problem formulated by Dr. Lamport, risks such as the tampered transactions and multiple spending of bitcoins are considered “traitors” (corresponding to a faulty calculator in a distributed environment), and solving the consensus-building problem within this environment can satisfy the conditions for Bitcoin. A failure in the distributed computing system resulting from the Byzantine generals problem is a “Byzantine Failure.” The Paxos algorithm is a family of protocols that solve the problems of consensus-building in a network of unreliable computers intended for coping with this failure. Dr. Lamport formulated the Paxos algorithm to cope with the computer failure and recovery problem; it is now utilized as a consensus-building protocol that updates data that is replicated within multiple data centers. In addition to the numerous achievements associated with his research on distributed systems mentioned above, Dr. Lamport also created LaTeX, a high-quality mathematical typesetting system that includes characteristic features designed for the production of academic documentation.
In the information and communications industry, computing systems in super-distributed environments are rapidly developing based on the internet and high-speed wireless connectivity. In the realization of these elements, the creation of a basic academic theory concerning distributed processing systems has had an enormous impact. In view of the contributions Dr. Lamport has made through his numerous research results and their applications, we believe that he would be an excellent recipient of the C&C Prize.