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 .