Zur Seitenansicht
 

Titelaufnahme

Titel
A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States
VerfasserBerenbrink, Petra ; Elsässer, Robert ; Friedetzky, Tom ; Kaaser, Dominik ; Kling, Peter ; Radzik, Tomasz
Erschienen in
32nd International Symposium on Distributed Computing (DISC 2018) / Schmid, Ulrich; Widder, Josef, Dagstuhl, 2018
Erschienen2018
SpracheEnglisch
Serie32nd International Symposium on Distributed Computing (DISC 2018) ; 121
DokumenttypAufsatz in einem Sammelwerk
Schlagwörter (EN)Population Protocols / Randomized Algorithms / Majority
Projekt-/ReportnummerP 27613
ISBN9783959770927
URNurn:nbn:at:at-ubs:3-11191 Persistent Identifier (URN)
DOI10.4230/LIPIcs.DISC.2018.10 
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States [0.48 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Englisch)

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

Statistik
Das PDF-Dokument wurde 2 mal heruntergeladen.
Lizenz
CC-BY-Lizenz (4.0)Creative Commons Namensnennung 4.0 International Lizenz