Paper Info
Title
Optimizing Threshold Protocols in Adversarial Structures
Abstract
Many replication protocols are using a threshold modelin which failures are independent and identically distributed (IID). In this model, one assumes that no more than tout of ncomponents can fail. In many real systems, however, failures are not IID, and a straightforward application of threshold protocols yields suboptimal results.Here, we examine the problem of optimally transforming threshold protocols into survivor-set protocols tolerating dependent failures. In particular, we are interested in threshold protocols where the number of components nand the number of failures tare related by n k·t, where kis a positive integer constant k. We develop an optimal transformationthat translates any such threshold protocol to a survivor-set dependent failure model, and hence, to adversarial structures. Our transformation does not require authentication, self-verification or encryption. We characterize equivalence classes of adversarial structures, regarding solvability, using certain hierarchical properties based on set intersection.
Year
DOI
Venue
2008
10.1007/978-3-540-87779-0_23
DISC
Keywords
Field
DocType
dependent failure,survivor-set protocol,n k,certain hierarchical property,threshold modelin,survivor-set dependent failure model,threshold protocols yield,threshold protocol,optimizing threshold protocols,adversarial structures,positive integer constant k,adversarial structure,independent and identically distributed,threshold model
Intersection (set theory),Integer,Authentication,Computer science,Real-time computing,NAND gate,Encryption,Independent and identically distributed random variables,Equivalence class,Threshold model,Distributed computing
Conference
Volume
ISSN
Citations 
5218
0302-9743
0
PageRank 
References 
Authors
0.34
22
4
Name
Order
Citations
PageRank
Maurice Herlihy18623920.94
Flavio P. Junqueira2103749.96
Keith Marzullo31930278.54
Lucia Draque Penso419620.46