A mesh network with a network-wide pre-shared key (PSK) that can be updated is described. The PSK can be used to establish secure communication between arbitrary electronic devices in the mesh network. In order to prevent electronic devices from being inadvertently ‘stranded,’ i.e., unable to securely communicate with other electronic devices in the mesh network when the PSK is updated, pairs of electronic devices in the mesh network establish personal PSKs (PPSKs). In particular, after securely associating with each other, a given pair of electronic devices may have used the current PSK to authenticate and encrypt their communication. Then, the given pair of electronic devices may define a PPSK, e.g., by exchanging one or more random numbers. If a subsequent attempt at establishing secure or encrypted communication between the given pair of electronic devices fails, these electronic devices may use the PPSK as a backup to establish the encrypted communication.