Contention Resolution under Selfishness
Contention Resolution under Selfishness
复制标题
自私下的争用解决
DOI：
10.1007/s00453-013-9773-4
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
Christodoulou G
中科院分区：
文献类型：
--
作者：
Christodoulou G
在许多通信设置中，例如有线和无线局域网，当多个用户尝试同时访问通信信道时，会导致冲突，并且没有一个通信成功。竞争解决是对分布式传输和重传协议的研究，该协议旨在最大化效用概念，例如在阻塞通信时的信道利用率。在设计此类协议时需要考虑的另一个问题是，如果另一种传输策略增加了用户的效用，则自私的用户可能会有偏离规定行为的动机。菲亚特等人的工作。(在SODA‘07，第179-188页，SIAM，费城2007)通过构建一个渐近最优的激励相容协议来解决这个问题。然而，他们的协议假设任何一次传输的代价为零，并且协议在非零传输代价下完全崩溃。在两种不同的信道反馈模型下，我们提出了对自私用户具有健壮性的渐近最优竞争解决协议。我们的主要结果是在冲突多重性反馈模型中，在每个时隙之后，尝试传输的次数作为反馈返回给用户。在这种情况下，我们给出了一个具有期望代价Θ(n+Clogn)且是ino(1)-均衡的协议，其中是用户数。
In many communications settings, such as wired and wireless local-area networks, when multiple users attempt to access a communication channel at the same time, a conflict results and none of the communications are successful. Contention resolution is the study of distributed transmission and retransmission protocols designed to maximize notions of utility such as channel utilization in the face of blocking communications.An additional issue to be considered in the design of such protocols is that selfish users may have incentive to deviate from the prescribed behavior, if another transmission strategy increases their utility. The work of Fiat et al. (in SODA ’07, pp. 179–188, SIAM, Philadelphia 2007) addresses this issue by constructing an asymptotically optimal incentive-compatible protocol. However, their protocol assumes the cost of any single transmission is zero, and the protocol completely collapses under non-zero transmission costs.In this paper we treat the case of non-zero transmission costc. We present asymptotically optimal contention resolution protocols that are robust to selfish users, in two different channel feedback models. Our main result is in the Collision Multiplicity Feedback model, where after each time slot, the number of attempted transmissions is returned as feedback to the users. In this setting, we give a protocol that has expected costΘ(n+clogn) and is ino(1)-equilibrium, wherenis the number of users.
登录
查看更多内容
影响因子：
2.2
作者：
Dandan Wang;C. Comaniciu;U. Tureli
通讯作者：
Dandan Wang;C. Comaniciu;U. Tureli
多服务器争用解决的实用退避协议分析
DOI：
10.1006/jcss.1998.1590
发表时间：
1996
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
L. A. Goldberg;P. MacKenzie
通讯作者：
P. MacKenzie
影响因子：
3.1
作者：
Mihály Geréb;Thanasis Tsantilas
通讯作者：
Thanasis Tsantilas
Erdöos-Rényi 型搜索方法如何为具有多重性反馈的随机访问提供速率 1 的显式代码构造
DOI：
10.1109/18.567769
发表时间：
1997
期刊：
IEEE Trans. Inf. Theory
影响因子：
--
作者：
M. Ruszinkó;P. Vanroose
通讯作者：
P. Vanroose
具有优先级和随机功率的时隙 Aloha
DOI：
10.1007/11422778_49
发表时间：
2005
期刊：
Comput. Networks
影响因子：
--
作者：
E. Altman;D. Barman;A. Benslimane;R. E. Azouzi
通讯作者：
R. E. Azouzi