OPTIMAL COTERIES AND VOTING SCHEMES

被引：13

作者：

DIKS, K

KRANAKIS, E

KRIZANC, D

MANS, B

PELC, A

机构：

[1] UNIV QUEBEC,DEPT INFORMAT,HULL J8X 3X7,QUEBEC,CANADA

[2] CARLETON UNIV,SCH COMP SCI,OTTAWA K1S 5B6,ONTARIO,CANADA

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 51卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

DISTRIBUTED SYSTEMS; FAULT TOLERANCE; AVAILABILITY; COTERIE; VOTING SCHEME;

D O I：

10.1016/0020-0190(94)00064-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider coteries (i.e. intersecting, Sperner systems) on arbitrary networks with given node reliability, which maximize the network availability (i.e. the probability that the set of operating nodes has a connected subgraph which contains a set from the coterie). We show that the singleton coterie is always optimal on any network when the node reliability is p less-than-or-equal-to 1/2. For p greater-than-or-equal-to 1/2, we give optimal coteries for the complete multipartite networks. The resulting optimal coteries when restricted to a special subclass of complete bipartite networks are shown to exceed the availability of any voting scheme, for p > 1/2.

引用

页码：1 / 6

页数：6

共 12 条

[1]

BARBARA D, 1987, IEEE T COMPUT, V36, P1197, DOI 10.1109/TC.1987.1676860

[2] INCREASING AVAILABILITY UNDER MUTUAL EXCLUSION CONSTRAINTS WITH DYNAMIC VOTE REASSIGNMENT [J].

BARBARA, D ;

GARCIAMOLINA, H ;

SPAUSTER, A .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1989, 7 (04) :394-426

[3] THE VULNERABILITY OF VOTE ASSIGNMENTS [J].

BARBARA, D ;

GARCIAMOLINA, H .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1986, 4 (03) :187-213

[4]

Bollobas B., 1986, COMBINATORICS SET SY

[5] HOW TO ASSIGN VOTES IN A DISTRIBUTED SYSTEM [J].

GARCIAMOLINA, H ;

BARBARA, D .

JOURNAL OF THE ACM, 1985, 32 (04) :841-860

[6]

Ibaraki T., 1991, Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing (Cat. No.91TH0396-2), P150, DOI 10.1109/SPDP.1991.218285

[7]

IBARAKI T, 1992, P 12 INT C DISTR COM, P650

[8] AVAILABILITY OF KAPPA-COTERIE [J].

KAKUGAWA, H ;

FUJITA, S ;

YAMASHITA, M ;

AE, T .

IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (05) :553-558

[9]

PAPADIMITRIOU C, 1993, COMMUNICATION

[10]

Papadimitriou C. H., 1991, Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, P75, DOI 10.1145/112600.112608

← 1 2 →