{'fraction_non_alphanumeric': 0.03365384615384615, 'fraction_numerical': 0.0, 'mean_word_length': 4.744827586206896, '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}}
A Distributed List Update

The list update problem is studied in a distributed environment where the set of items is partitioned across two processors and in which the cost of accessing an item is a combination of a list searching cost and a communication cost. A natural generalization of the Move-To-Front (MTF) algorithm, called Distributed Move-To-Front (DMTF), is analyzed under two models of information available to the algorithm. In the global knowledge model (DLUUGK]), the algorithm knows the partition of items in advance, while in the local knowledge model (DLUULK]), this information is unknown to the algorithm. Both competitive and expected value analyses are given. It is shown that for an n-item set, the performance of DMTF is a factor of O(n) worse in the local knowledge model than in the global knowledge model.