{'fraction_non_alphanumeric': 0.01568855316676351, 'fraction_numerical': 0.0005810575246949448, 'mean_word_length': 4.8175675675675675, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fighting against two adversaries: page migration in dynamic networks

Page migration is one of the fundamental subproblems in the framework of data management in networks. It occurs in a distributed network of processors sharing one indivisible memory page of size D, which is stored in one of the processors. During runtime, processors access unit size data items from the page, and the system is allowed to move the page from one processor to another in order to minimize the total communication cost.This problem was considered in the online setting numerous times by many researchers, and some online algorithms were proven to achieve a cost within a constant factor of the optimal offline solution. However, all results were achieved under the assumption that the communication costs between processors were fixed during the execution of the whole process.In this paper we consider a model in which the communication costs can change in each time step, but the pace of the changes is restricted. This is typical in mobile networks, and also models the dynamics of networks that are not exclusively dedicated to the page migration.If both changes of the network and the request sequence are given by some adversarial entity, we prove a tight bound on the competitive ratio of the problem. However, the size of this ratio motivates us to assume that the changes of communication costs are modeled by some stochastic process, and an adversary dictates only which processor issues a request. To analyze such a hybrid case, we introduce the notion of expected competitive ratio and prove that, for the case where constant number of processors perform a random walk on a torus or on a mesh of diameter √D, it is O(log2 D).