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 (��)).
| Identifer | oai:union.ndltd.org:MSSTATE/oai:scholarsjunction.msstate.edu:td-7348 |
| Date | 13 August 2024 |
| Creators | Biswas, Umesh Chandra |
| Publisher | Scholars Junction |
| Source Sets | Mississippi State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations |
Page generated in 0.002 seconds