Synchronizer (algorithm)
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a synchronizer is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
that can be used to run a
synchronous Synchronization is the coordination of events to operate a system in unison. For example, the conductor of an orchestra keeps the orchestra synchronized or ''in time''. Systems that operate with all parts in synchrony are said to be synchronou ...
algorithm on top of an asynchronous processor network, so enabling the
asynchronous system The primary focus of this article is asynchronous control in digital electronic systems. In a synchronous system, operations (instructions, calculations, logic, etc.) are coordinated by one, or more, centralized clock signals. An asynchronous ...
to run as a synchronous network. The concept was originally proposed in (Awerbuch, 1985) along with three synchronizer algorithms named alpha, beta and gamma which provided different tradeoffs in terms of time and message complexity. Essentially, they are a solution to the problem of asynchronous algorithms (which operate in a network with no global clock) being harder to design and often less efficient than the equivalent synchronous algorithms. By using a synchronizer, algorithm designers can deal with the simplified "ideal network" and then later mechanically produce a version that operates in more realistic asynchronous cases.


Available synchronizer algorithms

The three algorithms that Awerbuch provided in his original paper are as follows: * Alpha synchronizer: This has low time complexity but high message complexity. * Beta synchronizer: This has high time complexity but low message complexity. * Gamma synchronizer: This provides a reasonable tradeoff between alpha and beta by providing fairly low time and message complexity. Since the original paper, other synchronizer algorithms have been proposed in the literature.


References

* {{cite document , author=
Baruch Awerbuch Baruch Awerbuch (born 1958) is an Israeli-American computer scientist and a professor of computer science at Johns Hopkins University. He is known for his research on distributed computing. Academic biography Awerbuch was educated at the Technion ...
, title=Complexity of Network Synchronization , date=1985 , url=http://www.cs.uiowa.edu/~ghosh/synchronizer.pdf Distributed algorithms