The Disclosure Power of Shared Objects

Shared objects are the means by which processes gather and exchange information about the state of a distributed system. Objects that disclose more information about the system are therefore more desirable. In this paper, we propose the schedule reconstruction (SR) problem as a new metric for the disclosure power of shared memory objects. In schedule reconstruction, processes take steps which are interleaved to form a schedule; each process needs to be able to reconstruct the schedule up to its last step. We show that objects can be ranked in a hierarchy according to their ability to solve SR. In this hierarchy, stronger objects can implement weaker objects via a SR-based universal construction. We identify a connection between SR and consensus and prove that SR is at least as hard as consensus. Perhaps surprisingly, we show that objects that are powerful in solving consensus—such as compare-and-swap—are not always powerful in their ability to solve SR.

Presented at:
NETYS 2017, Marrakech, Morocco, May 17-19, 2017

Note: The status of this file is: Anyone

 Record created 2017-06-28, last modified 2020-05-19

Publisher's version:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)