Affordable Access

Publisher Website

Optimal coteries and voting schemes

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
51
Issue
1
Identifiers
DOI: 10.1016/0020-0190(94)00064-6
Keywords
  • Distributed Systems
  • Fault Tolerance
  • Availability
  • Coterie
  • Voting Scheme

Abstract

Abstract 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⩽ 1 2 . For p⩾ 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 .

There are no comments yet on this publication. Be the first to share your thoughts.