## 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 language | English |
---|---|

Pages (from-to) | 1-6 |

Number of pages | 6 |

Journal | Information Processing Letters |

Volume | 51 |

Issue number | 1 |

DOIs | |

Publication status | Published - 12 Jul 1994 |

Externally published | Yes |

## Keywords

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