Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
In this paper we study the behavior of deterministic algorithms when consensus is needed repeatedly, say k times. We show that it is possible to achieve consensus with the optimal number of processors (n > 3t), and when k is large enough, with optimal amortized cost in all other measures: the number of communication rounds r*, the maximal message size m*, and the total bit complexity b*. More specifically, we achieve the following amortized bounds for k consensus instances: r* = O(1 + t/k), b* = O(nt + nt3/k), and m* = O(1 + t2/k). When k ≥ t2, then r* and m* are O(1) and b*= O(nt), which is optimal. © 1995 Academic Press, Inc.
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
Nanda Kambhatla
ACL 2004
Michael D. Moffitt
ICCAD 2009
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)