Part of the book series:Lecture Notes in Computer Science ((LNCCN,volume 7960))
Included in the following conference series:
1227Accesses
Abstract
We consider the Secure Broadcast problem in incomplete networks. We study the resilience of the Certified Propagation Algorithm (CPA), which is particularly suitable forad hoc networks. We address the issue of determining the maximum number of corrupted players\(t^{\rm CPA}_{\rm max}\) that CPA can tolerate under thet-locally bounded adversary model, in which the adversary may corrupt at mostt players in each player’s neighborhood. For any graphG and dealer-nodeD we provide upper and lower bounds on\(t^{\rm CPA}_{\rm max}\) that can be efficiently computed in terms of a graph theoretic parameter that we introduce in this work. Along the way we obtain an efficient 2-approximation algorithm for\(t^{\rm CPA}_{\rm max}\). We further introduce two more graph parameters, one of which matches\(t^{\rm CPA}_{\rm max}\) exactly.
Work supported by ALGONOW project of the Research Funding Program THALIS, co-financed by the European Union (European Social Fund – ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF).
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dolev, D.: The byzantine generals strike again. J. Algorithms 3(1), 14–30 (1982)
Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly secure message transmission. J. ACM 40(1), 17–47 (1993),http://doi.acm.org/10.1145/138027.138036
Franklin, M., Wright, R.N.: Secure communication in minimal connectivity models. Journal of Cryptology 13, 9–30 (2000),http://dx.doi.org/10.1007/s001459910002
Garay, J.A., Moses, Y.: Fully polynomial byzantine agreement forn > 3t processors int + 1 rounds. SIAM J. Comput. 27(1), 247–290 (1998)
Ichimura, A., Shigeno, M.: A new parameter for a broadcast algorithm with locally bounded byzantine faults. Inf. Process. Lett. 110(12-13), 514–517 (2010)
Koo, C.Y.: Broadcast in radio networks tolerating byzantine adversarial behavior. In: Chaudhuri, S., Kutten, S. (eds.) PODC, pp. 275–282. ACM (2004)
Kranakis, E., Krizanc, D., Pelc, A.: Fault-tolerant broadcasting in radio networks. Journal of Algorithms 39(1), 47–67 (2001),http://www.sciencedirect.com/science/article/pii/S0196677400911477
Kumar, M.V.N.A., Goundan, P.R., Srinathan, K., Rangan, C.P.: On perfectly secure communication over arbitrary networks. In: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, PODC 2002, pp. 193–202. ACM, New York (2002),http://doi.acm.org/10.1145/571825.571858
Lamport, L., Shostak, R.E., Pease, M.C.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)
Pelc, A., Peleg, D.: Broadcasting with locally bounded byzantine faults. Inf. Process. Lett. 93(3), 109–115 (2005)
Tseng, L., Vaidya, N.H., Bhandari, V.: Broadcast using certified propagation algorithm in presence of byzantine faults. CoRR abs/1209.4620 (2012)
Author information
Authors and Affiliations
School of Electrical and Computer Engineering, National Technical University of Athens, 15780, Athens, Greece
Chris Litsas, Aris Pagourtzis & Dimitris Sakavalas
- Chris Litsas
You can also search for this author inPubMed Google Scholar
- Aris Pagourtzis
You can also search for this author inPubMed Google Scholar
- Dimitris Sakavalas
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Wrocłlaw University of Technology, ul. Janiszewskiego 14a, 50-372, Wrocłlaw, Poland
Jacek Cichoń
Wroclaw University of Technology, ul. Janiszewskiego 14a, 50-372, Wroclaw, Poland
Maciej Gȩbala
Institute of Mathematics and Computer Science, Wroclaw University of Technology, Poland
Marek Klonowski
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Litsas, C., Pagourtzis, A., Sakavalas, D. (2013). A Graph Parameter That Matches the Resilience of the Certified Propagation Algorithm. In: Cichoń, J., Gȩbala, M., Klonowski, M. (eds) Ad-hoc, Mobile, and Wireless Network. ADHOC-NOW 2013. Lecture Notes in Computer Science, vol 7960. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39247-4_23
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-39246-7
Online ISBN:978-3-642-39247-4
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative