Election in Fully Anonymous Shared Memory Systems: Tight Space Bounds and Algorithms

Damien Imbs, Michel Raynal, Gadi Taubenfeld

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

This article addresses election in fully anonymous systems made up of n asynchronous processes that communicate through atomic read-write registers or atomic read-modify-write registers. Given an integer d∈ { 1, ⋯, n- 1 }, two elections problems are considered: d-election (at least one and at most d processes are elected) and exact d-election (exactly d processes are elected). Full anonymity means that both the processes and the shared registers are anonymous. Memory anonymity means that the processes may disagree on the names of the shared registers. That is, the same register name A can denote different registers for different processes, and the register name A used by a process and the register name B used by another process can address the same shared register. Let n be the number of processes, m the number of atomic read-modify-write registers, and let M(n,d)={k:∀ℓ:1<ℓ≤n:gcd(ℓ,k)≤d}. The following results are presented for solving election in such an adversarial full anonymity context. It is possible to solve d-election when participation is not required if and only if m∈ M(n, d).It is possible to solve exact d-election when participation is required if and only if gcd(m, n) divides d.It is possible to solve d-election when participation is required if and only if gcd(m, n) ≤ d.Neither d-election nor exact d-election (be participation required or not) can be solved when the processes communicate through read-write registers only.

שפה מקוריתאנגלית
כותר פרסום המארחStructural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings
עורכיםMerav Parter
מוציא לאורSpringer Science and Business Media Deutschland GmbH
עמודים174-190
מספר עמודים17
מסת"ב (מודפס)9783031099922
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2022
פורסם באופן חיצוניכן
אירוע29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022 - Paderborn, גרמניה
משך הזמן: 27 יוני 202229 יוני 2022

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך13298 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022
מדינה/אזורגרמניה
עירPaderborn
תקופה27/06/2229/06/22

הערה ביבליוגרפית

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Election in Fully Anonymous Shared Memory Systems: Tight Space Bounds and Algorithms'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי