Name
Abstract | ||
|---|---|---|
We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original
namespace of the processors is unbounded, 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. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O(lg
n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in $$O(n lg^{2}\lceil N_{0}/n\rceil)$$ rounds, where N
0 is the value of the highest identifier among all the correct processors. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00446-007-0045-x | Distributed computing |
Keywords | Field | DocType |
Renaming problem,Byzantine failures,Synchronous message passing model | Discrete mathematics,Identifier,Computer science,Parallel computing,Petroleum engineering,Byzantine fault tolerance,Synchronous network,Message passing,Bounded function | Journal |
Volume | Issue | ISSN |
20 | 6 | 0178-2770 |
Citations | PageRank | References |
8 | 0.59 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Okun | 1 | 40 | 3.33 |
| Amnon Barak | 2 | 590 | 119.00 |
| Eli Gafni | 3 | 1598 | 145.07 |