The Opinion Number of Set-Agreement

Abstract : This paper carries on the effort to bridging runtime verification with distributed computabil- ity, studying necessary conditions for monitoring failure prone asynchronous distributed systems. In a previous paper (to appear in RV 2014), it has been proved that there are correctness prop- erties that require a large number of opinions (e.g., true, false, perhaps, probably true, probably no, etc.) to be monitored. The main outcome of this paper is that the need for this large num- ber of opinions is not an artifact induced by the existence of artificial constructions. Instead, monitoring an important class of properties, requiring processes to produce at most k different values does requires a large number of opinions. Specifically, our main result is a proof that it is impossible to monitor k-set-agreement in an n-process system with fewer than min{2k, n} + 1 opinions. The lower bound is shown to be tight.
Liste complète des métadonnées

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01073578
Contributor : Corentin Travers <>
Submitted on : Friday, October 10, 2014 - 10:12:15 AM
Last modification on : Friday, April 12, 2019 - 4:23:52 PM
Document(s) archivé(s) le : Sunday, January 11, 2015 - 10:25:42 AM

File

chcksa.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01073578, version 1

Citation

Pierre Fraigniaud, Sergio Rajsbaum, Matthieu Roy, Corentin Travers. The Opinion Number of Set-Agreement. OPODIS 2014 - 18th International Conference on Principles of Distributed Systems, Dec 2014, Cortina d’Ampezzo, Italy. pp.155-170. ⟨hal-01073578⟩

Share

Metrics

Record views

203

Files downloads

90