The multi-trials technique by Schneider et al. is employed for

distributed algorithms A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...

and allows breaking of 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 In computer science, message passing is a technique for invoking behavior (i.e., running a program) on a computer. The invoking program sends a message to a process (which may be an actor or object) and relies on that process and its supporti ...

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 In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

, 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 round. 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 (born 1953) 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 (UMIACS). Uzi Vishkin ...

Notes

References

* * {{Citation , last1=Schneider , first1=J. , contribution=A log-star distributed maximal independent set algorithm for growth-bounded graphs , title=Proceedings of the

Symposium on Principles of Distributed Computing The Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery (special interest groups SIGACT and SIGOPS). Scope and re ...

, year=2008 , contribution-url = https://www.tik.ee.ethz.ch/file/2be1291694b1730bba83f7fa18d9e0f2/podc08SW.pdf Graph theory Graph coloring Computational problems in graph theory