TY - CHAP

T1 - Fork-consistent constructions from registers

AU - Majuntke, M.

AU - Dobre, D.

AU - Cachin, C.

AU - Suri, Neeraj

PY - 2011

Y1 - 2011

N2 - Users increasingly execute services online at remote providers, but they may have security concerns and not always trust the providers. Fork-consistent emulations offer one way to protect the clients of a remote service, which is usually correct but may suffer from Byzantine faults. They feature linearizability as long as the service behaves correctly, and gracefully degrade to fork-consistent semantics in case the service becomes faulty. This guarantees data integrity and service consistency to the clients. All currently known fork-consistent emulations require the execution of non-trivial computation steps by the service. From a theoretical viewpoint, such a service constitutes a read-modify-write object, representing the strongest object in Herlihy's wait-free hierarchy [1]. A read-modify-write object is much more powerful than a shared memory made of so-called registers, which lie in the weakest class of all shared objects in this hierarchy. In practical terms, it is important to reduce the complexity and cost of a remote service implementation as computation resources are typically more expensive than storage resources. In this paper, we address the fundamental structure of a fork-consistent emulation and ask the question: Can one provide a fork-consistent emulation in which the service does not execute computation steps, but can be realized only by a shared memory? Surprisingly, the answer is yes. Specifically, we provide two such algorithms that can be built only from registers: A fork-linearizable construction of a universal type, in which operations are allowed to abort under concurrency, and a weakly fork-linearizable emulation of a shared memory that ensures wait-freedom when the registers are correct. © 2011 Springer-Verlag.

AB - Users increasingly execute services online at remote providers, but they may have security concerns and not always trust the providers. Fork-consistent emulations offer one way to protect the clients of a remote service, which is usually correct but may suffer from Byzantine faults. They feature linearizability as long as the service behaves correctly, and gracefully degrade to fork-consistent semantics in case the service becomes faulty. This guarantees data integrity and service consistency to the clients. All currently known fork-consistent emulations require the execution of non-trivial computation steps by the service. From a theoretical viewpoint, such a service constitutes a read-modify-write object, representing the strongest object in Herlihy's wait-free hierarchy [1]. A read-modify-write object is much more powerful than a shared memory made of so-called registers, which lie in the weakest class of all shared objects in this hierarchy. In practical terms, it is important to reduce the complexity and cost of a remote service implementation as computation resources are typically more expensive than storage resources. In this paper, we address the fundamental structure of a fork-consistent emulation and ask the question: Can one provide a fork-consistent emulation in which the service does not execute computation steps, but can be realized only by a shared memory? Surprisingly, the answer is yes. Specifically, we provide two such algorithms that can be built only from registers: A fork-linearizable construction of a universal type, in which operations are allowed to abort under concurrency, and a weakly fork-linearizable emulation of a shared memory that ensures wait-freedom when the registers are correct. © 2011 Springer-Verlag.

KW - atomic register

KW - Byzantine faults

KW - distributed system

KW - fork-consistency

KW - shared memory

KW - universal object

KW - Atomic register

KW - Byzantine fault

KW - Distributed systems

KW - Shared memories

KW - Model checking

KW - Online systems

KW - Semantics

KW - Network security

U2 - 10.1007/978-3-642-25873-2_20

DO - 10.1007/978-3-642-25873-2_20

M3 - Chapter

SN - 9783642258725

VL - 7109 LNCS

SP - 283

EP - 298

BT - Principles of Distributed Systems

ER -