The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] lock(1175hit)

1-20hit(1175hit)

  • Permissionless Blockchain-Based Sybil-Resistant Self-Sovereign Identity Utilizing Attested Execution Secure Processors Open Access

    Koichi MORIYAMA  Akira OTSUKA  

     
    INVITED PAPER

      Pubricized:
    2024/04/15
      Vol:
    E107-D No:9
      Page(s):
    1112-1122

    This article describes the idea of utilizing Attested Execution Secure Processors (AESPs) that fit into building a secure Self-Sovereign Identity (SSI) system satisfying Sybil-resistance under permissionless blockchains. Today’s circumstances requiring people to be more online have encouraged us to address digital identity preserving privacy. There is a momentum of research addressing SSI, and many researchers approach blockchain technology as a foundation. SSI brings natural persons various benefits such as owning controls; on the other side, digital identity systems in the real world require Sybil-resistance to comply with Anti-Money-Laundering (AML) and other needs. The main idea in our proposal is to utilize AESPs for three reasons: first is the use of attested execution capability along with tamper-resistance, which is a strong assumption; second is powerfulness and flexibility, allowing various open-source programs to be executed within a secure enclave, and the third is that equipping hardware-assisted security in mobile devices has become a norm. Rafael Pass et al.’s formal abstraction of AESPs and the ideal functionality $\color{brown}{\mathcal{G}_\mathtt{att}}$ enable us to formulate how hardware-assisted security works for secure digital identity systems preserving privacy under permissionless blockchains mathematically. Our proposal of the AESP-based SSI architecture and system protocols, $\color{blue}{\Pi^{\mathcal{G}_\mathtt{att}}}$, demonstrates the advantages of building a proper SSI system that satisfies the Sybil-resistant requirement. The protocols may eliminate the online distributed committee assumed in other research, such as CanDID, because of assuming AESPs; thus, $\color{blue}{\Pi^{\mathcal{G}_\mathtt{att}}}$ allows not to rely on multi-party computation (MPC), bringing drastic flexibility and efficiency compared with the existing SSI systems.

  • A Distributed Efficient Blockchain Oracle Scheme for Internet of Things Open Access

    Youquan XIAN  Lianghaojie ZHOU  Jianyong JIANG  Boyi WANG  Hao HUO  Peng LIU  

     
    PAPER-Network System

      Vol:
    E107-B No:9
      Page(s):
    573-582

    In recent years, blockchain has been widely applied in the Internet of Things (IoT). Blockchain oracle, as a bridge for data communication between blockchain and off-chain, has also received significant attention. However, the numerous and heterogeneous devices in the IoT pose great challenges to the efficiency and security of data acquisition for oracles. We find that the matching relationship between data sources and oracle nodes greatly affects the efficiency and service quality of the entire oracle system. To address these issues, this paper proposes a distributed and efficient oracle solution tailored for the IoT, enabling fast acquisition of real-time off-chain data. Specifically, we first design a distributed oracle architecture that combines both Trusted Execution Environment (TEE) devices and ordinary devices to improve system scalability, considering the heterogeneity of IoT devices. Secondly, based on the trusted node information provided by TEE, we determine the matching relationship between nodes and data sources, assigning appropriate nodes for tasks to enhance system efficiency. Through simulation experiments, our proposed solution has been shown to effectively improve the efficiency and service quality of the system, reducing the average response time by approximately 9.92% compared to conventional approaches.

  • Quantum Collision Resistance of Double-Block-Length Hashing Open Access

    Shoichi HIROSE  Hidenori KUWAKADO  

     
    PAPER-Cryptography and Information Security

      Pubricized:
    2024/03/04
      Vol:
    E107-A No:9
      Page(s):
    1478-1487

    In 2005, Nandi introduced a class of double-block-length compression functions hπ(x) := (h(x), h(π(x))), where h is a random oracle with an n-bit output and π is a non-cryptographic public permutation. Nandi demonstrated that the collision resistance of hπ is optimal if π has no fixed point in the classical setting. Our study explores the collision resistance of hπ and the Merkle-Damgård hash function using hπ in the quantum random oracle model. Firstly, we reveal that the quantum collision resistance of hπ may not be optimal even if π has no fixed point. If π is an involution, then a colliding pair of inputs can be found for hπ with only O(2n/2) queries by the Grover search. Secondly, we present a sufficient condition on π for the optimal quantum collision resistance of hπ. This condition states that any collision attack needs Ω(22n/3) queries to find a colliding pair of inputs. The proof uses the recent technique of Zhandry’s compressed oracle. Thirdly, we show that the quantum collision resistance of the Merkle-Damgård hash function using hπ can be optimal even if π is an involution. Finally, we discuss the quantum collision resistance of double-block-length compression functions using a block cipher.

  • Investigating and Enhancing the Neural Distinguisher for Differential Cryptanalysis Open Access

    Gao WANG  Gaoli WANG  Siwei SUN  

     
    PAPER-Information Network

      Pubricized:
    2024/04/12
      Vol:
    E107-D No:8
      Page(s):
    1016-1028

    At Crypto 2019, Gohr first adopted the neural distinguisher for differential cryptanalysis, and since then, this work received increasing attention. However, most of the existing work focuses on improving and applying the neural distinguisher, the studies delving into the intrinsic principles of neural distinguishers are finite. At Eurocrypt 2021, Benamira et al. conducted a study on Gohr’s neural distinguisher. But for the neural distinguishers proposed later, such as the r-round neural distinguishers trained with k ciphertext pairs or ciphertext differences, denoted as NDcpk_r (Gohr’s neural distinguisher is the special NDcpk_r with K = 1) and NDcdk_r , such research is lacking. In this work, we devote ourselves to study the intrinsic principles and relationship between NDcdk_r and NDcpk_r. Firstly, we explore the working principle of NDcd1_r through a series of experiments and find that it strongly relies on the probability distribution of ciphertext differences. Its operational mechanism bears a strong resemblance to that of NDcp1_r given by Benamira et al.. Therefore, we further compare them from the perspective of differential cryptanalysis and sample features, demonstrating the superior performance of NDcp1_r can be attributed to the relationships between certain ciphertext bits, especially the significant bits. We then extend our investigation to NDcpk_r, and show that its ability to recognize samples heavily relies on the average differential probability of k ciphertext pairs and some relationships in the ciphertext itself, but the reliance between k ciphertext pairs is very weak. Finally, in light of the findings of our research, we introduce a strategy to enhance the accuracy of the neural distinguisher by using a fixed difference to generate the negative samples instead of the random one. Through the implementation of this approach, we manage to improve the accuracy of the neural distinguishers by approximately 2% to 8% for 7-round Speck32/64 and 9-round Simon32/64.

  • Feistel Ciphers Based on a Single Primitive Open Access

    Kento TSUJI  Tetsu IWATA  

     
    PAPER-Cryptography and Information Security

      Pubricized:
    2024/03/29
      Vol:
    E107-A No:8
      Page(s):
    1229-1240

    We consider Feistel ciphers instantiated with tweakable block ciphers (TBCs) and ideal ciphers (ICs). The indistinguishability security of the TBC-based Feistel cipher is known, and the indifferentiability security of the IC-based Feistel cipher is also known, where independently keyed TBCs and independent ICs are assumed. In this paper, we analyze the security of a single-keyed TBC-based Feistel cipher and a single IC-based Feistel cipher. We characterize the security depending on the number of rounds. More precisely, we cover the case of contracting Feistel ciphers that have d ≥ 2 lines, and the results on Feistel ciphers are obtained as a special case by setting d = 2. Our indistinguishability security analysis shows that it is provably secure with d + 1 rounds. Our indifferentiability result shows that, regardless of the number of rounds, it cannot be secure. Our attacks are a type of a slide attack, and we consider a structure that uses a round constant, which is a well-known countermeasure against slide attacks. We show an indifferentiability attack for the case d = 2 and 3 rounds.

  • Dual-Path Convolutional Neural Network Based on Band Interaction Block for Acoustic Scene Classification Open Access

    Pengxu JIANG  Yang YANG  Yue XIE  Cairong ZOU  Qingyun WANG  

     
    LETTER-Engineering Acoustics

      Pubricized:
    2023/10/04
      Vol:
    E107-A No:7
      Page(s):
    1040-1044

    Convolutional neural network (CNN) is widely used in acoustic scene classification (ASC) tasks. In most cases, local convolution is utilized to gather time-frequency information between spectrum nodes. It is challenging to adequately express the non-local link between frequency domains in a finite convolution region. In this paper, we propose a dual-path convolutional neural network based on band interaction block (DCNN-bi) for ASC, with mel-spectrogram as the model’s input. We build two parallel CNN paths to learn the high-frequency and low-frequency components of the input feature. Additionally, we have created three band interaction blocks (bi-blocks) to explore the pertinent nodes between various frequency bands, which are connected between two paths. Combining the time-frequency information from two paths, the bi-blocks with three distinct designs acquire non-local information and send it back to the respective paths. The experimental results indicate that the utilization of the bi-block has the potential to improve the initial performance of the CNN substantially. Specifically, when applied to the DCASE 2018 and DCASE 2020 datasets, the CNN exhibited performance improvements of 1.79% and 3.06%, respectively.

  • Secrecy Outage Probability and Secrecy Diversity Order of Alamouti STBC with Decision Feedback Detection over Time-Selective Fading Channels Open Access

    Gyulim KIM  Hoojin LEE  Xinrong LI  Seong Ho CHAE  

     
    LETTER-Communication Theory and Signals

      Pubricized:
    2023/09/19
      Vol:
    E107-A No:6
      Page(s):
    923-927

    This letter studies the secrecy outage probability (SOP) and the secrecy diversity order of Alamouti STBC with decision feedback (DF) detection over the time-selective fading channels. For given temporal correlations, we have derived the exact SOPs and their asymptotic approximations for all possible combinations of detection schemes including joint maximum likehood (JML), zero-forcing (ZF), and DF at Bob and Eve. We reveal that the SOP is mainly influenced by the detection scheme of the legitimate receiver rather than eavesdropper and the achievable secrecy diversity order converges to two and one for JML only at Bob (i.e., JML-JML/ZF/DF) and for the other cases (i.e., ZF-JML/ZF/DF, DF-JML/ZF/DF), respectively. Here, p-q combination pair indicates that Bob and Eve adopt the detection method p ∈ {JML, ZF, DF} and q ∈ {JML, ZF, DF}, respectively.

  • A Sealed-Bid Auction with Fund Binding: Preventing Maximum Bidding Price Leakage Open Access

    Kota CHIN  Keita EMURA  Shingo SATO  Kazumasa OMOTE  

     
    PAPER

      Pubricized:
    2024/02/06
      Vol:
    E107-D No:5
      Page(s):
    615-624

    In an open-bid auction, a bidder can know the budgets of other bidders. Thus, a sealed-bid auction that hides bidding prices is desirable. However, in previous sealed-bid auction protocols, it has been difficult to provide a “fund binding” property, which would guarantee that a bidder has funds more than or equal to the bidding price and that the funds are forcibly withdrawn when the bidder wins. Thus, such protocols are vulnerable to a false bidding. As a solution, many protocols employ a simple deposit method in which each bidder sends a deposit to a smart contract, which is greater than or equal to the bidding price, before the bidding phase. However, this deposit reveals the maximum bidding price, and it is preferable to hide this information. In this paper, we propose a sealed-bid auction protocol that provides a fund binding property. Our protocol not only hides the bidding price and a maximum bidding price, but also provides a fund binding property, simultaneously. For hiding the maximum bidding price, we pay attention to the fact that usual Ethereum transactions and transactions for sending funds to a one-time address have the same transaction structure, and it seems that they are indistinguishable. We discuss how much bidding transactions are hidden. We also employ DECO (Zhang et al., CCS 2020) that proves the validity of the data to a verifier in which the data are taken from a source without showing the data itself. Finally, we give our implementation which shows transaction fees required and compare it to a sealed-bid auction protocol employing the simple deposit method.

  • A Mueller-Müller CDR with False-Lock-Aware Locking Scheme for a 56-Gb/s ADC-Based PAM4 Transceiver Open Access

    Fumihiko TACHIBANA  Huy CU NGO  Go URAKAWA  Takashi TOI  Mitsuyuki ASHIDA  Yuta TSUBOUCHI  Mai NOZAWA  Junji WADATSUMI  Hiroyuki KOBAYASHI  Jun DEGUCHI  

     
    PAPER

      Pubricized:
    2023/11/02
      Vol:
    E107-A No:5
      Page(s):
    709-718

    Although baud-rate clock and data recovery (CDR) such as Mueller-Müller (MM) CDR is adopted to ADC-based receivers (RXs), it suffers from false-lock points when the RXs handle PAM4 data pattern because of the absence of edge data. In this paper, a false-lock-aware locking scheme is proposed to address this issue. After the false-lock-aware locking scheme, a clock phase is adjusted to achieve maximum eye height by using a post-1-tap parameter for an FFE in the CDR loop. The proposed techniques are implemented in a 56-Gb/s PAM4 transceiver. A PLL uses an area-efficient “glasses-shaped” inductor. The RX comprises an AFE, a 28-GS/s 7-bit time-interleaved SAR ADC, and a DSP with a 31-tap FFE and a 1-tap DFE. A TX is based on a 7-bit DAC with a 4-tap FFE. The transceiver is fabricated in 16-nm CMOS FinFET technology, and achieves a BER of less than 1e-7 with a 30-dB loss channel. The measurement results show that the MM CDR escapes from false-lock points, and converges to near the optimum point for large eye height.

  • CRLock: A SAT and FALL Attacks Resistant Logic Locking Method for Controller at Register Transfer Level

    Masayoshi YOSHIMURA  Atsuya TSUJIKAWA  Toshinori HOSOKAWA  

     
    PAPER-VLSI Design Technology and CAD

      Pubricized:
    2023/09/04
      Vol:
    E107-A No:3
      Page(s):
    583-591

    In recent years, to meet strict time-to-market constraints, it has become difficult for only one semiconductor design company to design a VLSI. Thus, design companies purchase IP cores from third-party IP vendors and design only the necessary parts. On the other hand, since IP cores have the disadvantage that copyright infringement can be easily performed, logic locking has to be applied to them. Functional logic locking methods using TTLock are resilient to SAT attacks however vulnerable to FALL attacks. Additionally, it is difficult to design logic locking based on TTLock at the gate level. This paper proposes a logic locking method, CRLock, based on SAT attack and FALL attack resistance at the register transfer level. The CRLock is a logic locking method for controllers at RTL in which the designer selects a protected input pattern and modifies the controller based on the protection input pattern. In experimental results, we applied CRLock to MCNC'91 benchmark circuits and showed that all circuits are resistant to SAT and FALL attacks.

  • Flexible and Energy-Efficient Crypto-Processor for Arbitrary Input Length Processing in Blockchain-Based IoT Applications

    Vu-Trung-Duong LE  Hoai-Luan PHAM  Thi-Hong TRAN  Yasuhiko NAKASHIMA  

     
    PAPER

      Pubricized:
    2023/09/04
      Vol:
    E107-A No:3
      Page(s):
    319-330

    Blockchain-based Internet of Things (IoT) applications require flexible, fast, and low-power hashing hardware to ensure IoT data integrity and maintain blockchain network confidentiality. However, existing hashing hardware poses challenges in achieving high performance and low power and limits flexibility to compute multiple hash functions with different message lengths. This paper introduces the flexible and energy-efficient crypto-processor (FECP) to achieve high flexibility, high speed, and low power with high hardware efficiency for blockchain-based IoT applications. To achieve these goals, three new techniques are proposed, namely the crypto arithmetic logic unit (Crypto-ALU), dual buffering extension (DBE), and local data memory (LDM) scheduler. The experiments on ASIC show that the FECP can perform various hash functions with a power consumption of 0.239-0.676W, a throughput of 10.2-3.35Gbps, energy efficiency of 4.44-14.01Gbps/W, and support up to 8916-bit message input. Compared to state-of-art works, the proposed FECP is 1.65-4.49 times, 1.73-21.19 times, and 1.48-17.58 times better in throughput, energy efficiency, and energy-delay product (EDP), respectively.

  • Chained Block is NP-Complete

    Chuzo IWAMOTO  Tatsuya IDE  

     
    LETTER

      Pubricized:
    2023/10/23
      Vol:
    E107-D No:3
      Page(s):
    320-324

    Chained Block is one of Nikoli's pencil puzzles. We study the computational complexity of Chained Block puzzles. It is shown that deciding whether a given instance of the Chained Block puzzle has a solution is NP-complete.

  • MSLT: A Scalable Solution for Blockchain Network Transport Layer Based on Multi-Scale Node Management Open Access

    Longle CHENG  Xiaofeng LI  Haibo TAN  He ZHAO  Bin YU  

     
    PAPER-Network

      Pubricized:
    2023/09/12
      Vol:
    E107-B No:1
      Page(s):
    185-196

    Blockchain systems rely on peer-to-peer (P2P) overlay networks to propagate transactions and blocks. The node management of P2P networks affects the overall performance and reliability of the system. The traditional structure is based on random connectivity, which is known to be an inefficient operation. Therefore, we propose MSLT, a multiscale blockchain P2P network node management method to improve transaction performance. This approach involves configuring the network to operate at multiple scales, where blockchain nodes are grouped into different ranges at each scale. To minimize redundancy and manage traffic efficiently, neighboring nodes are selected from each range based on a predetermined set of rules. Additionally, a node updating method is implemented to improve the reliability of the network. Compared with existing transmission models in efficiency, utilization, and maximum transaction throughput, the MSLT node management model improves the data transmission performance.

  • Resource Allocation for Mobile Edge Computing System Considering User Mobility with Deep Reinforcement Learning

    Kairi TOKUDA  Takehiro SATO  Eiji OKI  

     
    PAPER-Network

      Pubricized:
    2023/10/06
      Vol:
    E107-B No:1
      Page(s):
    173-184

    Mobile edge computing (MEC) is a key technology for providing services that require low latency by migrating cloud functions to the network edge. The potential low quality of the wireless channel should be noted when mobile users with limited computing resources offload tasks to an MEC server. To improve the transmission reliability, it is necessary to perform resource allocation in an MEC server, taking into account the current channel quality and the resource contention. There are several works that take a deep reinforcement learning (DRL) approach to address such resource allocation. However, these approaches consider a fixed number of users offloading their tasks, and do not assume a situation where the number of users varies due to user mobility. This paper proposes Deep reinforcement learning model for MEC Resource Allocation with Dummy (DMRA-D), an online learning model that addresses the resource allocation in an MEC server under the situation where the number of users varies. By adopting dummy state/action, DMRA-D keeps the state/action representation. Therefore, DMRA-D can continue to learn one model regardless of variation in the number of users during the operation. Numerical results show that DMRA-D improves the success rate of task submission while continuing learning under the situation where the number of users varies.

  • Secure Enrollment Token Delivery Mechanism for Zero Trust Networks Using Blockchain Open Access

    Javier Jose DIAZ RIVERA  Waleed AKBAR  Talha AHMED KHAN  Afaq MUHAMMAD  Wang-Cheol SONG  

     
    PAPER

      Pubricized:
    2023/06/01
      Vol:
    E106-B No:12
      Page(s):
    1293-1301

    Zero Trust Networking (ZTN) is a security model where no default trust is given to entities in a network infrastructure. The first bastion of security for achieving ZTN is strong identity verification. Several standard methods for assuring a robust identity exist (E.g., OAuth2.0, OpenID Connect). These standards employ JSON Web Tokens (JWT) during the authentication process. However, the use of JWT for One Time Token (OTT) enrollment has a latent security issue. A third party can intercept a JWT, and the payload information can be exposed, revealing the details of the enrollment server. Furthermore, an intercepted JWT could be used for enrollment by an impersonator as long as the JWT remains active. Our proposed mechanism aims to secure the ownership of the OTT by including the JWT as encrypted metadata into a Non-Fungible Token (NFT). The mechanism uses the blockchain Public Key of the intended owner for encrypting the JWT. The blockchain assures the JWT ownership by mapping it to the intended owner's blockchain public address. Our proposed mechanism is applied to an emerging Zero Trust framework (OpenZiti) alongside a permissioned Ethereum blockchain using Hyperledger Besu. The Zero Trust Framework provides enrollment functionality. At the same time, our proposed mechanism based on blockchain and NFT assures the secure distribution of OTTs that is used for the enrollment of identities.

  • A Tunable Dielectric Resonator Oscillator with Phase-Locked Loop Stabilization for THz Time Domain Spectroscopy Systems

    Robin KAESBACH  Marcel VAN DELDEN  Thomas MUSCH  

     
    BRIEF PAPER

      Pubricized:
    2023/05/10
      Vol:
    E106-C No:11
      Page(s):
    718-721

    Precision microwave measurement systems require highly stable oscillators with both excellent long-term and short-term stability. Compared to components used in laboratory instruments, dielectric resonator oscillators (DRO) offer low phase noise with greatly reduced mechanical complexity. To further enhance performance, phase-locked loop (PLL) stabilization can be used to eliminate drift and provide precise frequency control. In this work, the design of a low-cost DRO concept is presented and its performance is evaluated through simulations and measurements. An open-loop phase noise of -107.2 dBc/Hz at 10 kHz offset frequency and 12.8 GHz output frequency is demonstrated. Drift and phase noise are reduced by a PLL, so that a very low jitter of under 29.6 fs is achieved over the entire operating bandwidth.

  • Non-Orthogonal Multiple Access Based on Orthogonal Space-Time Block Codes for Mobile Communications

    Yuyuan CHANG  Kazuhiko FUKAWA  

     
    PAPER-Terrestrial Wireless Communication/Broadcasting Technologies

      Pubricized:
    2023/04/17
      Vol:
    E106-B No:10
      Page(s):
    1024-1033

    Non-orthogonal multiple access (NOMA), which combines multiple user signals and transmits the combined signal over one channel, can achieve high spectral efficiency for mobile communications. However, combining the multiple signals can lead to degradation of bit error rates (BERs) of NOMA under severe channel conditions. In order to improve the BER performance of NOMA, this paper proposes a new NOMA scheme based on orthogonal space-time block codes (OSTBCs). The proposed scheme transmits several multiplexed signals over their respective orthogonal time-frequency channels, and can gain diversity effects due to the orthogonality of OSTBC. Furthermore, the new scheme can detect the user signals using low-complexity linear detection in contrast with the conventional NOMA. The paper focuses on the Alamouti code, which can be considered the simplest OSTBC, and theoretically analyzes the performance of the linear detection. Computer simulations under the condition of the same bit rate per channel show that the Alamouti code based scheme using two channels is superior to the conventional NOMA using one channel in terms of BER performance. As shown by both the theoretical and simulation analyses, the linear detection for the proposed scheme can maintain the same BER performance as that of the maximum likelihood detection, when the two channels have the same frequency response and do not bring about any diversity effects, which can be regarded as the worst case.

  • A 58-%-Lock-Range Divide-by-9 Injection-Locked Frequency Divider Using Harmonic-Control Technique

    Sangyeop LEE  Shuhei AMAKAWA  Takeshi YOSHIDA  Minoru FUJISHIMA  

     
    BRIEF PAPER

      Pubricized:
    2023/04/06
      Vol:
    E106-C No:10
      Page(s):
    529-532

    This paper presents a divide-by-9 injection-locked frequency divider (ILFD). It can lock onto about 6-GHz input with a locking range of 3.23GHz (58%). The basic concept of the ILFD is based on employing self-gated multiple inputs into the multiple-stage ring oscillator. A wide lock range is also realized by adapting harmonic-control circuits, which can boost specific harmonics generated by mixing. The ILFD was fabricated using a 55-nm deeply depleted channel (DDC) CMOS process. It occupies an area of 0.0210mm2, and consumes a power of 14.4mW.

  • An SOI-Based Lock-in Pixel with a Shallow Buried Channel for Reducing Parasitic Light Sensitivity and Improving Modulation Contrast

    Tatsuya KOBAYASHI  Keita YASUTOMI  Naoki TAKADA  Shoji KAWAHITO  

     
    PAPER

      Pubricized:
    2023/04/10
      Vol:
    E106-C No:10
      Page(s):
    538-545

    This paper presents a high-NIR sensitivity SOI-gate lock-in pixel with improved modulation contrast. The proposed pixel has a shallow buried channel and intermediate gates to create both a high lateral electric field and a potential barrier to parasitic light sensitivity. Device simulation results showed that parasitic light sensitivity reduced from 13.7% to 0.13% compared to the previous structure.

  • Feedback Node Sets in Pancake Graphs and Burnt Pancake Graphs

    Sinyu JUNG  Keiichi KANEKO  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2023/06/30
      Vol:
    E106-D No:10
      Page(s):
    1677-1685

    A feedback node set (FNS) of a graph is a subset of the nodes of the graph whose deletion makes the residual graph acyclic. By finding an FNS in an interconnection network, we can set a check point at each node in it to avoid a livelock configuration. Hence, to find an FNS is a critical issue to enhance the dependability of a parallel computing system. In this paper, we propose a method to find FNS's in n-pancake graphs and n-burnt pancake graphs. By analyzing the types of cycles proposed in our method, we also give the number of the nodes in the FNS in an n-pancake graph, (n-2.875)(n-1)!+1.5(n-3)!, and that in an n-burnt pancake graph, 2n-1(n-1)!(n-3.5).

1-20hit(1175hit)