A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Space-Optimal Population Protocols for Uniform Bipartition Under Global Fairness Protocolos populacionais com espaço ideal para bipartição uniforme sob justiça global

Hiroto YASUMI, Fukuhito OOSHITA, Ken'ichi YAMAGUCHI, Michiko INOUE

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Neste artigo, consideramos um problema de bipartição uniforme em um modelo de protocolo populacional. O objetivo do problema da bipartição uniforme é dividir uma população em dois grupos do mesmo tamanho. Estudamos o problema sob justiça global com várias suposições: 1) uma população com ou sem estação base, 2) protocolos simétricos ou assimétricos e 3) estados iniciais designados ou arbitrários. Como resultado, esclarecemos completamente a solubilidade do problema da bipartição uniforme sob justiça global e, se for solucionável, mostramos os limites superiores e inferiores rígidos do número de estados.

Publicação
IEICE TRANSACTIONS on Information Vol.E102-D No.3 pp.454-463
Data de publicação
2019/03/01
Publicitada
2018/10/30
ISSN online
1745-1361
DOI
10.1587/transinf.2018FCP0009
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Categoria

autores

Hiroto YASUMI
  Nara Institute of Science and Technology
Fukuhito OOSHITA
  Nara Institute of Science and Technology
Ken'ichi YAMAGUCHI
  National Institute of Technology, Nara College
Michiko INOUE
  Nara Institute of Science and Technology

Palavra-chave