Abstract:

In 1981, Gafni and Bertsekas presented a novel technique for
adapting to link changes in a distributed system, called "link
reversal".  Years later, this technique found application in
algorithms for mobile ad hoc networks.
In this talk, I will review the original link
reversal algorithms, discuss results on the work and time complexity
for link reversal algorithms (Busch, Surapaneni and Tirthapura),
and then survey several applications of this
technique to problems in distributed computing:
(1) Park and Corson applied link reversal in their routing algorithm
(TORA) for mobile ad hoc networks.
(2) The TORA algorithm was modified to solve the leader election
problem for mobile ad hoc networks (Malpani, Welch and Vaidya).
(3) Link reversal has been used in mutual exclusion and k-mutual
exclusion algorithms for mobile ad hoc networks (Walter, Welch and
Vaidya; Walter, Cao and Mohanty).
Finally, I will raise some open questions related to link reversal
algorithms.