Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: ANALYSIS OF AN ASYMMETRIC LEADER ELECTION ALGORITHM. | ANALYSIS OF AN ASYMMETRIC LEADER ELECTION ALGORITHM Svante Janson Department of Mathematics Uppsala University 75106 Uppsala Sweden svante.janson@math.uu.se Wojciech Szpankowski Department of Computer Science Purdue University W. Lafayette IN 47907 U.S.A. spa@cs.purdue.edu Submitted April 29 1997 Accepted July 14 1997. Abstract We consider a leader election algorithm in which a set of distributed objects people computers etc. try to identify one object as their leader. The election process is randomized that is at every stage of the algorithm those objects that survived so far flip a biased coin and those who received say a tail survive for the next round. The process continues until only one objects remains. Our interest is in evaluating the limiting distribution and the first two moments of the number of rounds needed to select a leader. We establish precise asymptotics for the first two moments and show that the asymptotic expression for the duration of the algorithm exhibits some periodic fluctuations and consequently no limiting distribution exists. These results are proved by analytical techniques of the precise analysis of algorithms such as analytical poissonization and depoissonization Mellin transform and complex analysis. 1 Introduction Consider a group of n people users computers objects etc. sharing a scarce resource e.g. channel CPU etc. . The following elimination process can be used to find a winner or a leader that has undisputed and uncontested access to the resource cf. bb fms prodinger All objects involved toss a biased coin and all players to throw heads are losers while those who throw tails remain candidate winners and flip the coins again until a single winner leader is identified. If all players throw heads at any stage the toss is inconclusive and all players participate again in the contest. How many tosses are needed to identify a winner The problem was The work of this author was supported by NSF Grants NCR-9206315 and NCR-9415491 and .
