首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Stabilization Time in Minority Processes
  • 本地全文:下载
  • 作者:P{'a}l Andr{'a}s Papp ; Roger Wattenhofer
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:149
  • 页码:1-19
  • DOI:10.4230/LIPIcs.ISAAC.2019.43
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We analyze the stabilization time of minority processes in graphs. A minority process is a dynamically changing coloring, where each node repeatedly changes its color to the color which is least frequent in its neighborhood. First, we present a simple Omega(n^2) stabilization time lower bound in the sequential adversarial model. Our main contribution is a graph construction which proves a Omega(n^(2-epsilon)) stabilization time lower bound for any epsilon>0. This lower bound holds even if the order of nodes is chosen benevolently, not only in the sequential model, but also in any reasonable concurrent model of the process.
  • 关键词:Minority process; Benevolent model
国家哲学社会科学文献中心版权所有