Scheduling for state-transfer updates

Under the state-transfer update model, the propagated updates involve an entirely new value. The arrival of a new update to a certain record makes any pending update to that same record worthless. That is, a replica can converge simply by applying the newest update but skipping any intermediate ones. This manner is suited for key-value stores with structureless values which are opaque blob-like objects where an application is responsible for the semantic interpretation of the read and write operations. In particular, each data object in key-value stores is accessed by its key leading to a clear relationship between the arriving queries and their corresponding pending updates. In this chapter (Part of this chapter are reprinted from Xu et al., DASFAA 1:86–100, 2013 [1], Xu et al., Distrib Parallel Databases 32(4):535–581, 2014 [2], with kind permission from Springer Science + Business Media.), based on a state-transfer model for update propagation, we present scheduling strategies for the efficient processing of both pending queries and updates at key-value data store nodes. In the following, Sect. 4.1 illustrates on-demand (OD) mechanism; Sect. 4.2 describes hybrid on-demand (HOD) mechanism; Sect. 4.3 presents freshness/tardiness (FIT) mechanism; Sect. 4.4 introduces adaptive freshness/tardiness (AFIT) mechanism; Sect. 4.5 introduces popularity-aware mechanism; Sect. 4.6 shows the design of simulation platform as well as experimental analysis; Sect. 4.7 summarizes this chapter.