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