TechTalks from event: IEEE IPDPS 2011

Note 1: Only plenary sessions (keynotes, panels, and best papers) are accessible without requiring log-in. For other talks, you will need to log-in using the email you registered for IPDPS 2011. Note 2: Many of the talks (those without a thumbnail next to the their description below) are yet to be uploaded. Some of them were not recorded because of technical problems. We are working with the corresponding authors to upload the self-recorded versions here. We sincerely thank all authors for their efforts in making their videos available.

SESSION 6: Self Stabilization and Security

  • A Lightweight Method for Automated Design of Convergence Authors: Ali Ebnenasir (Michigan Technological University, USA); Aly Farahat (Michigan Technological University, USA)
    Design and veri?cation of Self-Stabilizing (SS) network protocols are dif?cult tasks in part because of the requirement that a SS protocol must recover to a set of legitimate states from any state in its state space (when perturbed by transient faults). Moreover, distribution issues exacerbate the design complexity of SS protocols as processes should take local actions that result in global recovery/convergence of a network protocol. As such, most existing design techniques focus on protocols that are locally-correctable. To facilitate the design of ?nite-state SS protocols (that may not necessarily be locally-correctable), this paper presents a lightweight formal method supported by a software tool that automatically adds convergence to nonstabilizing protocols. We have used our method/tool to automatically generate several SS protocols with up to 40 processes (and 3 40 states) in a few minutes on a regular PC. Surprisingly, our tool has automatically synthesized both protocols that are the same as their manually-designed versions as well as new solutions for well-known problems in the literature (e.g., Dijkstra’s token ring [?]). Moreover, the proposed method has helped us reveal ?aws in a manually designed SS protocol.
  • Snap-Stabilizing Committee Coordination Authors: Borzoo Bonakdarpour (University of Waterloo, Canada); Stéphane Devismes (Université Joseph Fourier, France); Fran
    In this paper, we propose two snap-stabilizing distributed algorithms for the committee coordination problem. In this problem, a committee consists of a set of processes and committee meetings are synchronized, so that each process participates in at most one committee meeting at a time. Snap-stabilization is a versatile technique allowing to design algorithms that ef?ciently tolerate transient faults. Indeed, after a ?nite number of such faults (e.g. memory corruptions, message losses, etc), a snapstabilizing algorithm immediately operates correctly, without any external intervention. We design snap-stabilizing committee coordination algorithms enriched with some desirable properties related to concurrency, (weak) fairness, and a stronger synchronization mechanism called 2-Phase Discussion Time. From previous papers, we know that (1) in the general case, (weak) fairness cannot be achieved in the committee coordination, and (2) it becomes feasible provided that each process waits for meetings in?nitely often. Nevertheless, we show that even under this latter assumption, it is impossible to implement a fair solution that allows maximal concurrency. Hence, we propose two orthogonal snap-stabilizing algorithms, each satisfying 2-phase discussion time, and either maximal concurrency or fairness. The algorithm implementing fairness requires that every process waits for meetings in?nitely often. Moreover, for this algorithm, we introduce and evaluate a new ef?ciency criterion called the degree of fair concurrency. This criterion shows that even if it does not satisfy maximal concurrency, our snap-stabilizing fair algorithm still allows a high level of concurrency
  • SC-OA: A Secure and Efficient Scheme for Origin Authentication of Interdomain Routing in Cloud Computing Networks, Authors: Z. Le (Jiangxi University of Finance and Economics, China), N. Xiong (Georgia State University, USA), B. Yang (Jiangxi Universit
    IP pre?x hijacking is one of the top threats in the cloud computing Internets. Based on cryptography, many schemes for preventing pre?x hijacks have been proposed. Securing binding between IP pre?x and its owner underlies these schemes. We believe that a scheme for securing this binding should try to satisfy these seven critical requirements: no key escrow, no other secure channel, defending against Malicious Key Issuer (MKI) in the phase of pre?x announcement, defending against MKI in the phase of key issuing, no certi?cate, in-band delegation attestation, and in-band public key witness. In this paper, we propose a new scheme, Origin Authentication based on Self-Certi?ed public keys (SC-OA), using self-certi?ed public keys to authenticate origin autonomous systems. To the best of our knowledge, it is the ?rst work for securing pre?x ownership using self-certi?ed public keys to achieve an ef?cient and secure scheme that satis?es all seven requirements. The analyses show that SC-OA can defend against regular pre?x, subpre?x, unassigned pre?x, interception-based, and MKI hijacking, and improve performance in many aspects. It will be pushed ahead to practical deployment for preventing pre?x hijacks.