Self-stabilization in preference-based systems

被引:14
作者
Mathieu, Fabien [1 ]
机构
[1] Orange Labs, F-92794 Issy Les Moulineaux, France
关键词
Preference-based systems; b-matching; Self-stabilization; Speed of convergence;
D O I
10.1007/s12083-008-0009-3
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 [计算机科学与技术];
摘要
Participants of a decentralized system often use some local ranking informations, for selection of effective collaborations. We say that such systems are preference-based. For most practical types of preferences, such systems converge towards a unique stable configuration. In this paper, we investigate the speed and quality of the convergence process with respect to the model parameters. Our results provide an interesting insight into the design of system parameters, such as the number of connections or the algorithm for choosing new partners.
引用
收藏
页码:104 / 121
页数:18
相关论文
共 28 条
[1]
On a Generalization of the Stable Roommates Problem [J].
Cechlarova, Katarina ;
Fleiner, Tamas .
ACM TRANSACTIONS ON ALGORITHMS, 2005, 1 (01) :143-156
[2]
Cohen B, 2003, P2PECON
[3]
Random paths to stability in the roommate problem [J].
Diamantoudi, E ;
Miyagawa, E ;
Xue, LC .
GAMES AND ECONOMIC BEHAVIOR, 2004, 48 (01) :18-28
[4]
SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL [J].
DIJKSTRA, EW .
COMMUNICATIONS OF THE ACM, 1974, 17 (11) :643-644
[5]
Dolev S., 2000, Self-Stabilization
[6]
EDDINGTON A, 1928, GIFF LECT
[7]
FLEINER T, 2002, TR200208 EG RES GROU
[8]
GAI A, 2007, ICDCS
[9]
GAI A, 2006, ICON
[10]
GAI AT, 2007, EURO PAR