Efficient asynchronous distributed symmetry breaking
Baruch Awerbuch, Lenore Cowen, Mark A. Smith · 1994
Thw paper considers symmetry-breakhg in an aaynchronoue d~tributed network.We present and analyze a randomized protocol that constructs a maximal independent set in O(log n) expected time, and also a protocol for the dining philosophers problem that schedules a job that competes with 6 other jobs in expected 0(6) time, which is optimal.The beat previous algorithms for dining philosophers achieved only 0(62).In addition, the new protocols are 2-wait-/iwe which means that delays at a process are only dependent on processors or links at most distance two in the communication graph.1. Design a round-based protocol that performs well in a synchronous distributed network.