- 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
Keywords and Synonyms
Network synchronization; Low-stretch spanning subgraphs
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