{'fraction_non_alphanumeric': 0.028030578813250818, 'fraction_numerical': 0.0014561339643247178, 'mean_word_length': 5.273972602739726, '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}}
The Cost of Synchronizing Multiple-Access Channels

Multiple access channel is a communication model in which many users, also called stations, could exchange information. Since it offers limited capacity, some information sent through it might be lost due to signal interference (collision). Therefore, successful message delivery to a station requires breaking symmetry on the channel. In this work we consider the channel-synchronization problem on non-synchronized channels: assuming stations with messages wake-up dynamically on the channel, what is the minimum (expected) time needed for all stations to receive at least one message each. Historically, the first considered "classical" channel assumed that whenever two or more stations transmit simultaneously, the transmitted information is lost, otherwise it is delivered to all stations. In the seminal paper, Kushilevitz and Mansour proved that the first successful transmission on the channel with n contending stations may require, in the worst case, Ω(log n) expected communication rounds for any protocol. The result, however, holds under assumption that all contenders start their protocols at the same round. We prove that in more general scenario, in which the stations may have different local clocks and start the protocol at arbitrary times, the lower bound increases quadratically to Ω(log2 n) expected rounds. Both lower bounds are matched by corresponding algorithms developed in previous papers. Therefore, our lower bound proves the polynomial impact of synchronization on the classical multiple-access channels. Recently, more accurate channels based on Signal to Interference and Noise Ratio (SINR) were proposed and studied. The advantage of the SINR-based channel is that, apart of being closer to realistic physical scenario, some more demanding communication patterns could be scheduled in a single round. We support this intuition by showing that on such channel delivery of a message could be done faster than on the classical channel, mainly, in O(log2 n/log log n) expected number of rounds, thus separating the classical channel model from the SINR one. (The same time bound also holds with high probability.) Finally, we prove that for deterministic protocols receiving a message on the SINR channel requires time Ω(n), which surprisingly drops nearly exponentially to O(log2 n) if the stations have access to the global clock, which also separates SINR channel from the classic one, due to the lower bound Ω(n log n) on the latter. We also match the latter bound by corresponding lower bound. This together with our O(log2/log log n) round randomized algorithm, also proves a gap between deterministic and randomized solutions to the synchronization problem.