TAILIEUCHUNG - Báo cáo toán hoc:" Tight Bounds for Quasirandom Rumor Spreading Spyros Angelopoulos Benjamin Doerr Konstantinos Panagiotou Anna Huber"

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: Tight Bounds for Quasirandom Rumor Spreading Spyros Angelopoulos Benjamin Doerr Konstantinos Panagiotou Anna Huber. | Tight Bounds for Quasirandom Rumor Spreading Spyros Angelopoulos Benjamin Doerr Anna Huber Konstantinos Panagiotou Max-Planck-Institut fur Informatik 66123 Saarbrucken Germany sangelop bdoerr ahuber kpanagio @ Submitted Apr 29 2009 Accepted Jul 30 2009 Published Aug 7 2009 Mathematics Subject Classification 68Q87 68W20 68R05 60-08 Abstract This paper addresses the following fundamental problem Suppose that in a group of n people where each person knows all other group members a single person holds a piece of information that must be disseminated to everybody within the group. How should the people propagate the information so that after short time everyone is informed The classical approach known as the push model requires that in each round every informed person selects some other person in the group at random whom it then informs. In a different model known as the quasirandom push model each person maintains a cyclic list . permutation of all members in the group for instance a contact list of persons . Once a person is informed it chooses a random member in its own list and from that point onwards it informs a new person per round in the order dictated by the list. In this paper we show that with probability 1 o 1 the quasirandom protocol informs everybody in 1 o 1 log2 n ln n rounds furthermore we also show that this bound is tight. This result together with previous work on the randomized push model demonstrates that irrespectively of the choice of lists quasirandom broadcasting is as fast as broadcasting in the randomized push model up to lower order terms. At the same time it reduces the number of random bits from O log2 n to only log2 n per person. 1 Introduction Randomized Broadcast in Networks Information spreading in large networks is an important topic of study with several applications in distributed systems. Consider for instance the task of maintaining replicated databases on name servers in large networks 5 9 . Here the goal is to .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.