Abstract | ||
---|---|---|
We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when faulty processors are able to cheat about their original identities, this problem cannot be solved in an a priori bounded number of rounds for $t\geq(n+n\textrm{ mod }3)/3$, where n is the size of the network and t is the number of failures. This result also implies a $t\geq(n+n\textrm{ mod }4)/2$ bound for the case of faulty processors that are not able to falsify their original identities. In addition, we present several Byzantine renaming algorithms based on distinct approaches, each providing a different tradeoff between its running time and the solution quality. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11864219_2 | DISC |
Keywords | Field | DocType |
original identity,byzantine failure,bounded number,synchronous network,byzantine renaming,renaming problem,faulty processor,different tradeoff,distinct approach,solution quality,byzantine failures | Mod,Computer science,A priori and a posteriori,Byzantine fault tolerance,Real-time computing,Message passing,Synchronous network,Bounded function,Distributed computing | Conference |
Volume | ISSN | ISBN |
4167 | 0302-9743 | 3-540-44624-9 |
Citations | PageRank | References |
2 | 0.38 | 18 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Okun | 1 | 3 | 0.74 |
Amnon Barak | 2 | 590 | 119.00 |