- Free Articles
- Suffix Tree Construction in Hierarchical Memory Encyclopedia of Algorithms
- Probabilistic Data Forwarding in Wireless Sensor Networks Encyclopedia of Algorithms
- Renaming Encyclopedia of Algorithms
- Time in Philosophical Logic Encyclopedia of Database Systems
- Indoor Localization Encyclopedia of GIS
**More Free Articles**

This is the free portion of the full article.
The full article
is available to licensed users only.

How do I get access?

# Synchronizers, Spanners

## Keywords and Synonyms

Network synchronization; Low-stretch spanning subgraphs

## Problem Definition

Consider a communication network, modeled by an *n*-vertex undirected unweighted graph *G* = (*V*,*E*), for some positive integer *n*. Each vertex of *G* hosts a processor of unlimited computational power; the vertices have unique identity numbers, and they communicate via the edges of *G* by sending messages of size *O*(log *n*) each.

In the *synchronous* setting the communication occurs in discrete *rounds*, and a message sent in the beginning of a round *R* arrives at its destination before the round *R* ends. In the *asynchronous* setting each vertex maintains its own clock, and clocks of distinct vertices may disagree. It is assumed that each message sent (in the asynchronous detting) arrives at its destination within a certain time τ after it was sent, but the value of τ is not known to the processors.

It is generally much easier to devise algorithms that apply to the synchronous