Some highlights of prior work include algorithms and impossibility
results for distributed consensus, resource allocation, leader
election, clock synchronization, self-stabilizing computation,
reliable communication over unreliable networks, admission control and
routing.
A New Lower Bound for Mutual Exclusion
Virtual
Nodes for Mobile Ad Hoc Networks
A
Correctness Condition for Memory Shared by Byzantine Processes
Hoest and
Shavit's work on
asynchronous
complexity.
Shavit's work on
asynchronous computability.
Lynch's new book,
Distributed Algorithms,
which presents a large
collection of distributed algorithms and lower bound results, in a
unified automata-theoretic framework.
A research contribution in this text
is a modular treatment of fault-tolerant asynchronous algorithms
(using composition and various general transformations).
Shvartsman
with colleagues obtained several interesting results for
fault-tolerant
and efficient parallel algorithms.
A monograph
synthesizing the latest in algorithmics,
lower bounds and simulations goes in print this February.
Shavit's work on
distributed-coordinated data structures.
Shavit and Zemach
have designed diffracting tree algorithms and analyzed their
complexity.
Lynch,
Shavit,
Shvartsman
and Touitou have characterized the
timing
conditions for linearizability of counting networks. They have
performed a comprehensive set of simulations and used the theoretical
results to explain the observations.
Shavit and Della-Libera have designed
reactive
diffracting trees.
De Prisco, Lampson, and
Lynch have studied the
Paxos
algorithm, which is a practical algorithm for distributed
consensus invented by Lamport.
Chlebus, De Prisco and
Shvartsman have provided new algorithms
for executing tasks in distributed systems where processors can
fail and restart.
Patt-Shamir's recent
PhD thesis
on clock synchronization algorithms
and lower bound results.
Lynch and
Rajsbaum's new
treatment of the Borowsky-Gafni simulation algorithm.
Kleinberg, Attiya and Lynch's results on the inherent time
tradeoffs between message delivery time and quiesce time. for
connection management.
