Theses and Dissertations

Advisor

Young, Maxwell

Committee Member

Banicescu, Ioana

Committee Member

Mittal, Sudip

Date of Degree

8-13-2024

Original embargo terms

Immediate Worldwide Access

Document Type

Graduate Thesis - Open Access

Major

Computer Science (Research Computer Science)

Degree Name

Master of Science (M.S.)

College

James Worth Bagley College of Engineering

Department

Department of Computer Science and Engineering

Abstract

Contention resolution coordinates access to a shared communication channel divided into synchronized slots. For any fixed slot, a packet can be sent, leading to three outcomes: empty (no packet sent), successful (one packet sent), or collision (multiple packets sent). Each slot provides ternary feedback: empty, successful, or collision. Much of the prior work has mainly focused on optimizing the makespan, the number of slots needed for all packets to succeed. However, in many modern systems, collisions also incur time costs, which existing algorithms do not address. In this thesis, we design and analyze a randomized contention-resolution algorithm, Collision-Evasion Backoff, that optimizes both the makespan and the cost of collisions. In our research, �� ≥ 2 packets are initially present in the system, and each collision has a known cost C, where 1 ≤ C ≤ ���� for a known ��. With error probability polynomially small in ��, Collision-Evasion Backoff guarantees that all packets succeed with makespan �� (��√C log(��)) and a total expected collision cost of �� (��√C log2 (��)).

Download

Share

COinS