Abstract
I first became involved in Distributed Computing Theory around 1978 or 1979, as a new professor at Georgia Tech. Looking back at my first few years in the field, approximately 1979-1982, I see that they were tremendously exciting, productive, and fun. I collaborated with, and learned from, many leaders of the field, including Mike Fischer, Jim Burns, Michael Merritt, Gary Peterson, Danny Dolev, and Leslie Lamport.
Results that emerged during that time included space lower bounds for mutual exclusion; definition of the k-exclusion problem, with associated lower bounds and algorithms; the Burns-Lynch lower bound on the number of registers needed for mutual exclusion; fast network-wide resource allocation algorithms; the Lynch-Fischer semantic model for distributed systems (a precursor to I/O automata); early work on proof techniques for distributed algorithms; lower bounds on the number of rounds for Byzantine agreement; definition of the approximate agreement problem and associated algorithms; and finally, the Fischer-Lynch-Paterson impossibility result for consensus.
In this talk, I will review this early work, trying to explain how we were thinking at the time, and how the ideas in these projects influenced later work.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lynch, N. (2007). DISC 20th Anniversary: Invited Talk My Early Days in Distributed Computing Theory: 1979-1982. In: Pelc, A. (eds) Distributed Computing. DISC 2007. Lecture Notes in Computer Science, vol 4731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75142-7_47
Download citation
DOI: https://doi.org/10.1007/978-3-540-75142-7_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75141-0
Online ISBN: 978-3-540-75142-7
eBook Packages: Computer ScienceComputer Science (R0)