NDLI: The Cost of Synchronizing Multiple-Access Channels

Please wait, while we are loading the content...

Cortical Computation

Near-Optimal Scheduling of Distributed Algorithms

Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata

Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication

A (Truly) Local Broadcast Layer for Unreliable Radio Networks

Algebraic Methods in the Congested Clique

The "Mobile Adversary" Paradigm in Distributed Computation and Systems

Trading Fences with RMRs and Separating Memory Models

Impossibility Results for Distributed Transactional Memory

How Fair is Your Protocol?: A Utility-based Approach to Protocol Optimality

Randomized Proof-Labeling Schemes

Online Resource Leasing

Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks

The Weakest Failure Detector for Eventual Consistency

On the Push&Pull Protocol for Rumour Spreading: [Extended Abstract]

Towards Optimal Synchronous Counting

Scheduling Loop-free Network Updates: It's Good to Relax!

Fast and Exact Majority in Population Protocols

Near-Optimal Distributed Maximum Flow: Extended Abstract

Efficient Communication in Cognitive Radio Networks

Fast Partial Distance Estimation and Applications

The Price of being Adaptive

Disjoint-Access Parallelism: Impossibility, Possibility, and Cost of Transactional Memory Implementations

Lock-Free Algorithms under Stochastic Schedulers

Adaptively Secure Computation with Partial Erasures

Distributed Convex Thresholding

On Information Complexity in the Broadcast Model

Limitations of Highly-Available Eventually-Consistent Data Stores

Distributed Resource Discovery in Sub-Logarithmic Time

Fault-Tolerant Consensus in Directed Graphs

New Routing Techniques and their Applications

Distributed House-Hunting in Ant Colonies

Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST

A Local Broadcast Layer for the SINR Network Model

Brief Announcement: Distributed Single-Source Reachability

On the Time and Space Complexity of ABA Prevention and Detection

Safety-Liveness Exclusion in Distributed Computing

Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way

Improved Analysis of Deterministic Load-Balancing Schemes

Brief Announcement: Average Complexity for the LOCAL Model

How To Elect a Leader Faster than a Tournament

Computing Weak Consistency in Polynomial Time: [Extended Abstract]

The Cost of Synchronizing Multiple-Access Channels

Minimal Synchrony for Byzantine Consensus

Brief Announcement: Routing the Internet with Very Few Entries

Brief Announcement: On the Feasibility of Leader Election and Shape Formation with Self-Organizing Programmable Matter

Fast Distributed Almost Stable Matchings

Brief Announcement: Fast and Simple Node Coloring in the SINR Model

Brief Announcement: A Hierarchy of Congested Clique Models, from Broadcast to Unicast

Brief Announcement: Fault-tolerant Broadcast in Anonymous Distributed Systems with Fair Lossy Communication Channels

Brief Announcement: Eventually Consistent Linearizability

On the Space Complexity of Set Agreement?

Brief Announcement: Robust and Private Distributed Shared Atomic Memory in Message Passing Networks

Brief Announcement: Investigating the Cost of Anonymity on Dynamic Networks

Leveraging Multiple Channels in Ad Hoc Networks

Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems: Extended abstract

Dual Failure Resilient BFS Structure

The Cost of Synchronizing Multiple-Access Channels

Content Provider	ACM Digital Library
Author	Stachowiak, Grzegorz Jurdzinski, Tomasz
Abstract	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 $Ω(log^{2}$ 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(log^{2}$ 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(log^{2}$ 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(log^{2}/log$ log n) round randomized algorithm, also proves a gap between deterministic and randomized solutions to the synchronization problem.
Starting Page	421
Ending Page	430
Page Count	10
File Format	PDF
ISBN	9781450336178
DOI	10.1145/2767386.2767439
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-07-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Sinr channel Multiple-access channel Symmetry-breaking Synchronization problem
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in