------------------------------------------------------------------------------- B O S T O N U N I V E R S I T Y Computer Science Department C O L L O Q U I U M Wednesday November 16, 1994 3:00pm (Coffee served at 2:30pm) Seminar Room / MCS 135 ------------------------------------------------------------------------------- Fast and Lean Self-Stabilizing Asynchronous Protocols Gene Itkis (Technion, Boston University) We consider asynchronous general topology dynamic networks of identical nameless nodes with worst-case transient faults. Starting from any faulty configuration, our protocols self-stabilize any computation in time polynomial in the (unknown) network diameter. A slope is an mapping from nodes to {0, -1,+1} inducing a natural orientation of the edges, such that there are no unbalanced cycles (i.e. those with more up edges than down). Slope has much greater utility when centered, i.e., has a unique node, leader, with no down edges. It then yields a BFS tree the construction/maintenance of which is known to self-stabilize many basic network management protocols (we generalize this experience to all randomized linear space problems). Initiating an (uncentered) slope is an easy task and we give a simple fast deterministic algorithm for it (BFS with a few precautions). For simplicity, it takes larger (log of diameter) space per node than the more cumbersome O(1) protocol which we will only sketch. The main task, leader election (i.e. modifying any slope into a centered one), is much harder and known to be impossible for deterministic algorithms. Our main result gives a fast randomized algorithm for it, using one byte per node and a pointer to its edge. The third protocol, Interface (using no additional space) runs the first two as subroutines. It assures that any (consistent with it) variation in either of the first two protocols cannot affect the other one. Joint work with Leonid Levin. Host: Prof. Leonid Levin ------------------------------------------------------------------------------- For more information contact Prof. Azer Bestavros . ------------------------------------------------------------------------------- Directions to Boston University's MCS Building ---------------------------------------------- SOUTH /\ /||\ E || W A /---/\---\ E S \---\/---/ S T || T \||/ \/ NORTH Engineering Building Psychology ------------] [------------------------------------] [-------------------. | .---> Cummington Street (one-way) | | | ----------. | .------] [-----------] [-----------] [-------------. | | | | | #111 Computer Info | | | | | | Science Tech | | `---- | |Warren `----------------------------' | | |Garage | | | | .---- | | .-----------------. | | | |---------. | Warren Towers | | | | |Taco Bell| | (700 Comm. Ave) | | | ----------' `-------------------] [-( )-] [--------------------' `---- ^ | |o| Commonwealth Avenue |o| `---- |o| <------------------ |o| <--- |o| (One-way East) |o| --------------------------------------------------------------------. .---- ## BU-East T-stop ## | | ============================================================================== | | | | | | | | | | | | | | | | | | | ============================================================================== <-- Inbound (to Downtown) | | Green Line | | --> Outbound (to Boston College) | | ============================================================================== | | | | | | | | | | | | | | | | | | | ============================================================================== ## BU-East T-stop ## | | --------------------------------------------------------------------' `---- Commonwealth Avenue |o| ------------------> |o| (One-way West) |o|