Multi-trials technique
Encyclopedia
The multi-trials technique by Schneider et al. is employed for distributed algorithms
and allows to break symmetry efficiently. Symmetry breaking is necessary, for instance, in resource allocation problems, where many entities want to access the same resource concurrently. Many message passing
algorithms typically employ one attempt to break symmetry per message exchange. The multi-trials technique transcends this approach through employing more attempts with every message exchange.
For example, in a simple algorithm for computing an O(Δ) vertex coloring, where Δ denotes the maximum degree in the graph, every uncolored node randomly picks an available color and keeps it if no neighbor (concurrently) chooses the same color. For the multi-trials technique, a node gradually increases the number of chosen colors in every communication rounds. The technique can yield more than an exponential reduction in the required communication rounds. However, if the maximum degree Δ is small more efficient techniques exist, e.g. the (extended) coin-tossing technique by Richard Cole and Uzi Vishkin
.
Distributed algorithms
A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in many varied application areas of distributed computing, such as telecommunications, scientific computing, distributed information processing,...
and allows to break symmetry efficiently. Symmetry breaking is necessary, for instance, in resource allocation problems, where many entities want to access the same resource concurrently. Many message passing
Message passing
Message passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
algorithms typically employ one attempt to break symmetry per message exchange. The multi-trials technique transcends this approach through employing more attempts with every message exchange.
For example, in a simple algorithm for computing an O(Δ) vertex coloring, where Δ denotes the maximum degree in the graph, every uncolored node randomly picks an available color and keeps it if no neighbor (concurrently) chooses the same color. For the multi-trials technique, a node gradually increases the number of chosen colors in every communication rounds. The technique can yield more than an exponential reduction in the required communication rounds. However, if the maximum degree Δ is small more efficient techniques exist, e.g. the (extended) coin-tossing technique by Richard Cole and Uzi Vishkin
Uzi Vishkin
Uzi Vishkin is a computer scientist at the University of Maryland, College Park, where he is Professor of Electrical and Computer Engineering at the University of Maryland Institute for Advanced Computer Studies . Uzi Vishkin is known for his work in the field of parallel computing...
.