TAILIEUCHUNG - Báo cáo toán học: "ANALYSIS OF AN ASYMMETRIC LEADER ELECTION ALGORITHM"

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 Wojciech Szpankowski Department of Computer Science Purdue University W. Lafayette IN 47907 . spa@ 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 . 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 .

• Báo cáo khoa học
• tài liệu báo cáo nghiện cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội