Minimal cryptosystems and defining subliminal-freeness
Yvo Desmedt, Moti Yung
ISIT 1994
Performing work in parallel by a multitude of processes in a distributed environment is currently a fast growing area of computer applications (due to its cost effectiveness). Adaptation of such applications to changes in system's parallelism (i.e., the availability of processes) is essential for improved performance and reliability. In this work we consider one aspect of coping with dynamic processes failures in such a setting, namely the following scenario formulated by Dwork, Halpern and Waarts [DHW92]: a system of n synchronous processes that communicate only by sending messages to one another. These processes must perform m independent units of work. Processes may fail by crashing and wait-freeness is required, i.e. that whenever at least one process survives, all m units of work will be performed. We consider the notion of fast algorithms in this setting, yet we are not willing to trade improved time for a high cost in communication. Thus, we require message efficiency as well. We therefore put forth the notion of lexicographic efficiency, that is we consider the following two complexity measures in order: The parallel processor step (or S for short) as introduced by Kanellakis and Shvartsman [KS89] in the context of robust PRAM and the number of messages sent (denoted M).
Yvo Desmedt, Moti Yung
ISIT 1994
Tushar Chandra, Vassos Hadzilacos, et al.
PODC 1994
Rafail Ostrovsky, Moti Yung
PODC 1991
Alfredo de Santis, Giovanni Di Crescenzo, et al.
FOCS 1994