Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Corentin Travers Connect in order to contact the contributor
Submitted on : Friday, October 10, 2014 - 10:12:15 AM
Last modification on : Monday, July 4, 2022 - 8:58:55 AM
Long-term archiving on: : Sunday, January 11, 2015 - 10:25:42 AM


Files produced by the author(s)


  • HAL Id : hal-01073578, version 1


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⟩



Record views


Files downloads