Go to page
 

Bibliographic Metadata

Title
A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States
AuthorBerenbrink, Petra ; Elsässer, Robert ; Friedetzky, Tom ; Kaaser, Dominik ; Kling, Peter ; Radzik, Tomasz
Published in
32nd International Symposium on Distributed Computing (DISC 2018) / Schmid, Ulrich; Widder, Josef, Dagstuhl, 2018
Published2018
LanguageEnglish
Series32nd International Symposium on Distributed Computing (DISC 2018) ; 121
Document typeArticle in a collected edition
Keywords (EN)Population Protocols / Randomized Algorithms / Majority
Project-/ReportnumberP 27613
ISBN9783959770927
URNurn:nbn:at:at-ubs:3-11191 Persistent Identifier (URN)
DOI10.4230/LIPIcs.DISC.2018.10 
Restriction-Information
 The work is publicly available
Files
A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States [0.48 mb]
Links
Reference
Classification
Abstract (English)

A population protocol is a sequence of pairwise interactions of n agents. During one interaction, two randomly selected agents update their states by applying a deterministic transition function. The goal is to stabilize the system at a desired output property. The main performance objectives in designing such protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem, which uses Theta(log n) states (per agent) and stabilizes in O(log

Stats
The PDF-Document has been downloaded 2 times.
License
CC-BY-License (4.0)Creative Commons Attribution 4.0 International License