A Note on Set Agreement with Omission Failures1 1This work is partially supported by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant number 5005-67322
| Autor: | Petr Kouznetsov, Bastian Pochon, Rachid Guerraoui |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Discrete mathematics
General Computer Science media_common.quotation_subject 010102 general mathematics Structure (category theory) 0102 computer and information sciences Characterization (mathematics) 01 natural sciences Upper and lower bounds Agreement Theoretical Computer Science Set (abstract data type) 010201 computation theory & mathematics Simple (abstract algebra) 0101 mathematics Mathematics media_common Computer Science(all) |
| Zdroj: | Electronic Notes in Theoretical Computer Science. 81:48-58 |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/s1571-0661(04)80835-1 |
| Popis: | This paper considers the k-set agreement problem in a synchronous distributed system model with send-omission failures in which at most f processes can fail by send-omission. We show that, in a system of n+1 processes (n+1) f), no algorithm can solve k-set agreement in ⌊ fk ⌋ rounds. Our lower bound proof uses topological techniques to characterize subsets of executions of our model. The characterization has a surprisingly regular structure which leads to a simple and succinct proof. We also show that the lower bound is tight by exhibiting a new algorithm that solves k-set agreement in ⌊ fk ⌋ + 1 rounds. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect