Authentication safety: safe on-demand concurrent authentication under transient faults and arbitrary initialization

Abstract In this paper, we propose a novel, safe, and fault-tolerant on-demand concurrent authentication algorithm that concurrently verifies authentication requests of multiple processes by checking the legitimacy (or safety) of the server processes and those in the communication path between the requesters and their servers to implement propagation safety in the presence of transient faults and upon starting in an arbitrary system configuration. A server is the central trusted computing entity providing some services to the other processes in a communication network. A transient fault refers to a fault that perturbs the state of system processes but not their programs. Since the algorithm is safe, it ensures that authentication for a process is always achieved iff all the processes between the process and its corresponding server process are safe. Due to being able to start in an arbitrary system configuration, the proposed algorithm is scalable and does not require a reset or an initial setup. The on-demand property of the algorithm ensures that the authentication is activated only if some authentication requests are present. The authentication starts upon a request without a delay and takes $O(n)$ rounds, where $n$ is the height of the broadcast tree.