My Ph.D. thesis was in self-stabilization and my advisors were Nancy Lynch and Baruch Awerbuch from whom I learned to love the field of distributed algorithms. Both, of course, were remarkable people: Nancy won the Knuth Prize and Baruch won the Dijkstra Prize.


When I worked at DEC, the head of the DECNET Architecture group, Tony Lauck, often insisted that we make all our protocols self-stabilizing though we did not do any proofs. So it was natural that for my Ph.D., I began to be interested in general techniques for self-stabilization (as opposed to ad hoc techniques for each specific problem). There was a general approach by Katz and Perry which seemed too inefficient; so I worked with colleagues on creating less general but more efficient techniques.

Self-stabilization by Local Checking and Correction. . When and how Local Checking and Correction suffices. Final journal paper based on FOCS 1991a paper and my Ph.D. thesis. One of 12 references in Wikipedia article on self-stabilization.

Self-stabilization by Distributed Program Checking. Baruch Awerbuch and George Varghese. FOCS 1991b. A way of making Baruch's synchronizer self-stabilizing so we could make any synchronous protocol self-stabilizing. Some effort is devoted to this topic in Dolev's book on Self-Stabilization. I can't find an online version.

Self-stabilization by Local Checking and Network Reset., WDAG - 94. Completes the local checking saga by showing that any locally checkable protocol can be made self-stabilizing using a reset protocol. Proof details can be found in my thesis.

Summary of Ph.D. Thesis on Self-stabilization. . Should be easier to read than the thesis itself!

Self-stabilization by counter flushing. . Self-stabilization using a fresh counter value. SIAM Journal of Computation 2000 based on paper in PODC 1994. Abstracts a technique used implicitly in Dijkstra's seminal paper.

Self-stabilization by Window Washing. . PODC 1996. Shows how to make window protocols self-stabilizing and applies this idea to flow control and ATM broadcast protocols. Generalizes counter flushing.

Compositional Proofs of Self-stabilizing Protocols. . 3rd Workshop on Self-stabilization, 1997.

A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock, Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, George Varghese, IEEE Trans. Dependable Sec. Comput. 4(3): 180-190, 2007. One of 12 references in Wikipedia article on self-stabilization.

Distributed Algorithms

I continued to work on distributed algorithms with students Adam Costello and Mahesh Jayaram at Washington University until I realized it was hard to find students jobs after writing such papers! Thereafter, I concentrated on networking though the distributed algorithms point of view has always influenced me, with the 2012 paper on Header Space coming closest to this way of looking at the world in recent times.

A Tradeoff between Safety and Liveness for Randomized Coordinated Attack. PODC 92 and Information and Computation, July 96, shows the (in)effectiveness of randomization in curing the impossibility of coordinated attack. Chapter 5 in Lynch's book on Distributed Computing is devoted to these results. 

Fault Span of Crash Failures. . Shows crash faults can drive systems to arbitrarily muddled states. Journal of the ACM (JACM) 2000, based on papers in PODC 1996 and PODC 1997. PODC 96 paper won best student paper award. Justifies the need for self-stabilizing protocols.

An Error Control Scheme for Large Scale Multicast Applications. . Scalable reliable multicast with minimal router assistance. Full version based on Infocom 98 paper.

Route Flap Damping Exacerbates Internet Routing Convergence}. , We show that a well-known BGP Mechanisms for improved stability using hysteresis (Route Flap Damping) has undesirable interactions with route convergence. We explore this phenomenon and describe a solution to the problem. SIGCOMM 2002. One of 13 references in Wikipedia article on BGP.

Header Space Analysis: Static Checking for Networks , P. Kazemanian, G. Varghese, N. McKeown, NSDI 2012. A geometric model for network processing and its use to check network configurations for errors.

Prepared by George Varghese,
Last Modified Feb 2012.