Optimal coteries and voting schemes

Krzysztof Diks*, Evangelos Kranakis, Danny Krizanc, Bernard Mans, Andrzej Pelc

*Corresponding author for this work

Research output: Contribution to journalArticle

16 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1-6
Number of pages6
JournalInformation Processing Letters
Volume51
Issue number1
DOIs
Publication statusPublished - 12 Jul 1994
Externally publishedYes

Keywords

  • Availability
  • Coterie
  • Distributed systems
  • Fault tolerance
  • Voting scheme

Fingerprint Dive into the research topics of 'Optimal coteries and voting schemes'. Together they form a unique fingerprint.

Cite this