000226211 001__ 226211
000226211 005__ 20190317000641.0
000226211 037__ $$aREP_WORK
000226211 245__ $$aThe Disclosure Power of Shared Objects
000226211 269__ $$a2017
000226211 260__ $$c2017
000226211 300__ $$a15
000226211 336__ $$aReports
000226211 520__ $$aShared 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—and thus provide a more centralized view—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.
000226211 700__ $$aBlanchard, Peva François
000226211 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000226211 700__ $$0248775$$g253970$$aStainer, Julien Michel
000226211 700__ $$0249111$$g192870$$aZablotchi, Mihail Igor
000226211 8564_ $$uhttps://infoscience.epfl.ch/record/226211/files/disclosure-power.pdf$$zn/a$$s201780$$yn/a
000226211 909C0 $$xU10407$$0252114$$pDCL
000226211 909CO $$ooai:infoscience.tind.io:226211$$qGLOBAL_SET$$pIC$$preport
000226211 917Z8 $$x192870
000226211 917Z8 $$x192870
000226211 917Z8 $$x192870
000226211 917Z8 $$x192870
000226211 937__ $$aEPFL-REPORT-226211
000226211 973__ $$aEPFL
000226211 980__ $$aREPORT