Multiple access communication has played a crucial role in the operation of many networked systems, including satellite networks, radio networks, wired/wireless Local Area Networks (LANs), and data centers. One important feature of multiple access communication is its decentralized information structure. In general, when multiple users share the communication system, coordination among them is essential to resolve collision issues. In the absence of a centralized controller, it is challenging to design efficient user coordination mechanisms. We consider a typical slotted multiple access communication system where multiple users share a common collision channel. Each user is equipped with an infinite size buffer and observes Bernoulli arrivals to its own queue. In addition to the local information, all users receive a common broadcast feedback from the channel. The feedback indicates whether the previous transmission was successful, or it was a collision, or the channel was idle. The objective is to design a transmission protocol that effectively coordinates the users transmissions under the above described information structure. In this talk, we propose a common information based multiple access protocol (CIMA) that uses the common channel feedback to coordinate users. In CIMA, each user constructs upper bounds on the lengths of the queues of all users, including itself, based on previous transmission strategies and the common feedback. Since the upper bounds are common knowledge, users can coordinate their transmission through these common upper bounds to avoid collision. We prove that without knowledge of any statistics, CIMA achieves the full throughput region of the collision channel. We also prove that the CIMA protocol incurs low transmission delay; the delay is upper-bounded by a linear function of the number of users.
Bio: Yi Ouyang received the B.S. degree in Electrical Engineering from the National Taiwan University, Taipei, Taiwan in 2009. He is currently a Ph.D. candidate in Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor, MI, USA. His research interests include stochastic scheduling, decentralized stochastic control and dynamic stochastic games with asymmetric information.