Optimal coteries and voting schemes

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


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
Issue number1
Publication statusPublished - 12 Jul 1994
Externally publishedYes


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


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

Cite this