We resolve one of the longest-standing open problems in the field of autonomous mobile robots, disproving the established conjecture, and refute the natural belief that self-consistency cannot help the robots coordinate.

• We study the Gathering problem for n mobile robots endowed with two-color lights in semi-synchronous (Ssynch) environments. • We focus on two models: F ST A (where robots see only their own light) and F COM (where robots see only each others’ lights). • We prove existing upper bounds to be optimal. In particular, we show that, even with rigid movement and consistent chirality, Gathering is impossible with only 2 colors in both F ST A and F COM under Ssynchunless additional assumptions are introduced. • We provide a constructive algorithm demonstrating that, relying on minimal extra assumptions, F ST A robots with 2 colors can solve Gathering in Ssynch. We study the problem Gathering for n autonomous mobile robots in semi-synchronous settings with a persistent memory called light . It is well known that Gathering is impossible in the basic model ( OBLOT ) where robots have no lights, even if the system is semi-synchronous (called Ssynch ). Gathering becomes possible, however, if each robot has a light of some type that can be set to a constant number of colors. In the F COM model, the robots can only see the lights of other robots. In the F ST A model, each robot can only observe its own light. In the LUMI model, all robots can see all lights. This paper focuses on F ST A robots with 2-colored lights in synchronous settings. We show that 2-color F ST A and F COM robots cannot solve Gathering in Ssynch without additional assumptions, even with rigid movement and agreement on chirality. We also show a Gathering algorithm for F ST A robots with 2-color Ssynch with minimal additional assumptions.

ABSTRACT An autonomous mobile robot system is a distributed system consisting of multiple mobile computational entities, called robots, which autonomously and repeatedly perform three fundamental operations: look, compute, and move. Various challenges in such systems, including gathering, pattern formation, and flocking, have been extensively studied to explore the relationship between the robots' capabilities and the feasibility of solving these problems (i.e., solvability). In this study, we focus on the complete visibility problem, which aims to relocate all robots on an infinite grid plane so that every robot is visible to every other robot (i.e., complete visibility). We assume that each robot is a luminous robot (i.e., has a light with a constant number of colors) and opaque (non‐transparent). This paper primarily examines the number of light colors required for each robot to solve the complete visibility problem. Specifically, we investigate the question: “how many colors can we reduce while still achieving complete visibility?” (even under certain stronger assumptions). As an answer to the above question, we show the existence of a deterministic algorithm to achieve complete visibility (i.e., every robot can observe all the other robots) using only two colors of light, if the robots agree on the directions and orientations of both axes. The proposed algorithm correctly works even if robots operate asynchronously and have no knowledge of the total number of robots. Moreover, its spatial complexity (i.e., the area of the smallest enclosed rectangle that includes all robots in the final configuration) ensures the optimal one, , where is the number of robots.

We present an enhanced GPU implementation of the H-P sort algorithm, which is a widely used method for integer sorting based on histogram computation and prefix sum calculation. This work extends a previous high-performance GPU version of the algorithm, presented at the 2021 ICPP international conference. Through algorithmic refinements and optimizations, we demonstrate significant performance improvements compared to the conventional H-P sort. It achieves a maximum speedup of 3.45x over conventional H-P Sort. Furthermore, in scenarios where the H-P sort had previously lagged behind the fastest available library, our improved implementation now surpasses it in terms of execution speed. This advancement in GPU-based sorting techniques contributes to more efficient data processing in various computational applications, emphasizing the practical significance of this work.

Research on distributed computing by a team of identical mobile computational entities, called robots, operating in a Euclidean space in $\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$ ($\mathit{LCM}$) cycles, has recently focused on better understanding how the computational power of robots depends on the interplay between their internal capabilities (i.e., persistent memory, communication), captured by the four standard computational models (OBLOT, LUMI, FSTA, and FCOM) and the conditions imposed by the external environment, controlling the activation of the robots and their synchronization of their activities, perceived and modeled as an adversarial scheduler. We consider a set of adversarial asynchronous schedulers ranging from the classical semi-synchronous (SSYNCH) and fully asynchronous (ASYNCH) settings, including schedulers (emerging when studying the atomicity of the combination of operations in the $\mathit{LCM}$ cycles) whose adversarial power is in between those two. We ask the question: what is the computational relationship between a model $M_1$ under adversarial scheduler $K_1$ ($M_1(K_1)$) and a model $M_2$ under scheduler $K_2$ ($M_2(K_2)$)? For example, are the robots in $M_1(K_1)$ more powerful (i.e., they can solve more problems) than those in $M_2(K_2)$? We answer all these questions by providing, through cross-model analysis, a complete characterization of the computational relationship between the power of the four models of robots under the considered asynchronous schedulers. In this process, we also provide qualified answers to several open questions, including the outstanding one on the proper dominance of SSYNCH over ASYNCH in the case of unrestricted visibility.

Summary In this article, we consider the case in which a swarm of robots collaborates in a mission, where a few of the robots behave maliciously. These malicious Byzantine robots may be temporally or constantly controlled by an adversary. The scope is synchronized full information robot operations, where a robot that does not follow the program/policy of the swarm is immediately identified and can be remembered as Byzantine. As robots may be suspected of being Byzantine due to benign temporal malfunctions, it is imperative to forgive and forget, otherwise, a robot cannot assume collaborative actions with any other robot in the swarm. Still, remembering for a while may facilitate a policy of surrounding, isolating and freezing the movement of the misbehaving robots, by several robots, allowing the rest to perform the swarm task with no intervention. We demonstrate the need to periodically forgive and forget to realize swarm several tasks including patrolling/cleaning in the presence of possible Byzantine robots. The policy for achieving the task consists of blocking the movement of the Byzantine robot(s) by some of the robots, while the rest patrol/clean the plane.

The MapReduce framework has firmly established itself as one of the most widely used parallel computing platforms for processing big data on tera- and peta-byte scale. Approaching it from a theoretical standpoint has proved to be notoriously difficult, however. In continuation of Goodrich et al.'s early efforts, explicitly espousing the goal of putting the MapReduce framework on footing equal to that of long-established models such as the PRAM, we investigate the obvious complexity question of how the computational power of MapReduce algorithms compares to that of combinational Boolean circuits commonly used for parallel computations. Relying on the standard MapReduce model introduced by Karloff et al. a decade ago, we develop an intricate simulation technique to show that any problem in NC (i.e., a problem solved by a logspace-uniform family of Boolean circuits of polynomial size and a depth polylogarithmic in the input size) can be solved by a MapReduce computation in O(T(n)/log⁡n) rounds, where n is the input size and T(n) is the depth of the witnessing circuit family. Thus, we are able to closely relate the standard, uniform NC hierarchy modeling parallel computations to the deterministic MapReduce hierarchy DMRC by proving that NCi+1⊆DMRCi for all i∈N. Besides the theoretical significance, this result has important applied aspects as well. In particular, we show for all problems in NC1—many practically relevant ones, such as integer multiplication and division, the parity function, and recognizing balanced strings of parentheses being among these—how to solve them in a constant number of deterministic MapReduce rounds.

We study the problem Rendezvous for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors [10], [21]. With external-lights, robots can only observe the state of the lights of other robots. With internal-lights, robots can only observe their own light, and full-lights combine both. This paper focuses on robots with external-lights in asynchronous settings and considers a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and 3 colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors [10]. This paper, extending the impossibility result, shows that there exists no L-algorithm in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC in which no robot can execute more than 1 Look operation between the Look and its subsequent Compute operations of another robot. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.

In this paper, we propose integer sorting algorithms based on histogram and prefix-sums and we show that their GPU-implementations are faster than the fastest sorting GPU-implementations in Thrust and/or CUB library for several input data. In particular, our algorithm is very useful in the cases that the maximum value of input data is smaller than the number of input data and/or the number of kinds of input data is smaller than the maximum value of input data.

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

The paper details the first successful attempt at using model checking techniques to verify the correctness of distributed algorithms for robots evolving in a continuous environment. The study focuses on the problem of rendezvous of two robots with lights.There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g., FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between robots activation schedules.The paper presents a generic verification model written for the SPIN model checker. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model checker are consistent with the results known in the literature. The model checker outputs a counter-example execution in every case that is known to fail.In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem for luminous rendezvous algorithms.

Compressive sensing (CS) is data acquiring and innovative mathematical approach that accelerate and efficient sampling from large into small volumes of data. Moreover, it could be dramatically reduced amounts of sensor, power consumption, storage size, and bandwidth which results in lower hardware costs [1]. In wireless cameras network for video surveillance, the large amount of data is produced. However, there is still a lot of redundant data in measurement domain. To solve this problem, coding techniques such as block-based CS (BCS), intra-prediction and quantization is applied to avoid higher rate-distortion than other CS frameworks. Therefore, new imaging architecture has been proposed to be sensed, removed redundant information, and compressed simultaneously, thus leading to the faster image acquisition system.

The MapReduce framework has firmly established itself as one of the most widely used parallel computing platforms for processing big data on tera- and peta-byte scale. Approaching it from a theoretical standpoint has proved to be notoriously difficult, however. In continuation of Goodrich et al.’s early efforts, explicitly espousing the goal of putting the MapReduce framework on footing equal to that of long-established models such as the PRAM, we investigate the obvious complexity question of how the computational power of MapReduce algorithms compares to that of combinational Boolean circuits commonly used for parallel computations. Relying on the standard MapReduce model introduced by Karloff et al. a decade ago, we develop an intricate simulation technique to show that any problem in NC (i.e., a problem solved by a logspace-uniform family of Boolean circuits of polynomial size and a depth polylogarithmic in the input size) can be solved by a MapReduce computation in O(T(n)/log n) rounds, where n is the input size and T(n) is the depth of the witnessing circuit family. Thus, we are able to closely relate the standard, uniform NC hierarchy modeling parallel computations to the deterministic MapReduce hierarchy DMRC by proving that NC^{i+1} subseteq DMRC^i for all i in N. Besides the theoretical significance, this result has important applied aspects as well. In particular, we show for all problems in NC^1 - many practically relevant ones, such as integer multiplication and division and the parity function, being among these - how to solve them in a constant number of deterministic MapReduce rounds.

We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operate in the 2-dimensional Euclidean plane in synchronous Look-Compute-Move (LCM) cycles. Specifically, we focus on the power of persistent memory and that of explicit communication, and on their computational relationship. In the most common model, OBLOT, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the LUMI model, each robot is equipped with a constant-sized persistent memory (called light), visible to all the robots; hence, these luminous robots are capable in each cycle of both remembering and communicating. Since luminous robots are computationally more powerful than the standard oblivious one, immediate important questions are about the individual computational power of persistent memory and of explicit communication. In particular, which of the two capabilities, memory or communication, is more important? in other words, is it better to remember or to communicate ? In this paper we address these questions, focusing on two sub-models of LUMI: FSTA, where the robots have a constant-size persistent memory but are silent; and FCOM, where the robots can communicate a constant number of bits but are oblivious. We analyze the relationship among all these models and provide a complete exhaustive map of their computational relationship. Among other things, we prove that communication is more powerful than persistent memory under the fully synchronous scheduler Fsynch, while they are incomparable under the semi-synchronous scheduler Ssynch.

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

The paper details the first successful attempt at using model-checking techniques to verify the correctness of distributed algorithms for robots evolving in a \emph{continuous} environment. The study focuses on the problem of rendezvous of two robots with lights. There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g., FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between robots activation schedules. The paper presents a generic verification model written for the SPIN model-checker. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model-checker are consistent with the results known in the literature. The model-checker outputs a counter-example execution in every case that is known to fail. In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem for luminous rendezvous algorithms.

In this paper, we define a new concept neighborhood mutual remainder (NMR). An NMR distributed algorithms should satisfy global fairness, l-exclusion and repeated local rendezvous requirements. We give a simple self-stabilizing algorithm to demonstrate the design paradigm to achieve NMR, and also present applications of NMR to a Look-Compute-Move robot system.

We study the Rendezvous problem for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors. If robots can observe not only their own lights but also other robots' lights, their lights are called full-light. If robots can only observe the state of other robots' lights, the lights are called external-light. This paper focuses on robots with external-lights in asynchronous settings and a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and three colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors. In this paper, extending the impossibility result, we show that there exist no L-algorithms in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC and other robots can execute at most one Look operation between the Look operation of a robot and its subsequent Compute operation. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.

Anonymous mobile robots are often classified into synchronous, semi-synchronous, and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. (All patterns formable with memory are formable without memory for synchronous robots, and little is known for asynchronous robots.) However, the gathering problem for two semi-synchronous robots without memory (called oblivious robots in this paper) is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely, static compasses with (possibly incorrect) constant bearings and dynamic compasses the bearings of which can change arbitrarily (immediately before a new look-compute-move cycle starts and after the last cycle ends). For each of the combinations of robot and compass models, we establish the condition on deviation $\phi$ that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: $\phi < \pi/2$ for semi-synchronous and asynchronous robots with static compasses, $\phi < \pi/4$ for semi-synchronous robots with dynamic compasses, and $\phi < \pi/6$ for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

It is known that Byzantine consensus algorithms guarantee one-step decision only in favorable situations (e.g. when all processes propose the same value) and no one-step algorithm can support two-step decision. This paper presents DEX, a novel one-step Byzantine algorithm that circumvents these impossibilities using the condition-based approach. Algorithm DEX has two distinguished features: Adaptiveness and Double-expedition property. Adaptiveness makes it sensitive to only actual number of failures so that it provides fast termination for more number of inputs when there are fewer failures (a common case in practice). The double-expedition property facilitates two-step decision in addition to one-step decision by running two condition-based mechanisms in parallel. To the best of our knowledge, double-expedition property is the new concept introduced by this paper, and DEX is the first algorithm having such a feature. Although DEX takes four steps at worst in well-behaved runs while existing one-step algorithms take only three, it is expected to work efficiently because the worst-case does not occur so often in practice.

In this paper, we have proposed a time efficient, energy saving and robust broadcast/multicast protocol for reconfigurable cluster-based sensor network. In our broadcast protocol, a broadcast can be executed in O(hd2+ D2) rounds and each node needs to be awake in O(D2) rounds, where D and d are the degrees of G and the sub-network induced by the network backbone, respectively, and h is the height of the backbone. When k channels are available, the broadcast can be executed in O((hd2+ D2)/k) rounds and each. We show that our broadcast protocol can be readily modified to the one for multicast. The cluster-based architecture used in this paper for a sensor network is an improved version. The proposed network architecture is self-constructible and self-reconfigurable by using two topological management operations: node-move-in and node-move-out. Details of the protocol along with experimental results are discussed. Simulation results show that the protocol performance is much better than that in the theoretical analysis.

We consider the problem of distributed deterministic broadcasting in synchronous radio networks whose topology and size are unknown. Radio networks can be modeled by directed graphs. It has been shown that there does not exist any algorithm of acknowledged radio broadcasting (ARB) on the model without a collision detection even if graphs are restricted to symmetric ones, where ARB is a broadcasting task in which a distinguished node(called source) transmits a source message to all nodes and it confirms that all nodes have received the source message. In this paper, on the model of radio networks with a collision detection, we show an O(r + ecc) time deterministic ARB algorithm for symmetric graphs, where r is the length of the source message and ecc is the largest distance from the source to any other node.

Given a collection of segments in the plane, if we regard the segments as opaque barriers, their upper envelope consists of the portions of the segments visible from point (0, +/spl infin/). In this paper, we present deterministic parallel methods for constructing the upper envelope of segments on the weakest shared-memory model, the EREW PRAM. We show that we can find the upper envelope of n line segments optimally in 0(logn) time using 0(n) processors. Furthermore, if the segments are nonintersecting and their endpoints are sorted in x-coordinate, then we can reduce the number of processors to 0(n/ logn). Our method implies that we can find the upper envelope sequentially in 0(n log log n) time, which improves previous results. We also show that we can find the upper envelope of n k-intersecting segments (any pair of the segments intersects at most k times) with a slightly larger time and processor bound.

Given a collection of segments in the plane that intersect pairwise at most k times, regarding the segments as opaque barriers, their upper envelope consists of the portions of the segments visible from point (0,+/spl infin/). We give efficient parallel methods for finding the upper envelope of k-intersecting segments for any integer k/spl ges/0, in the weakest shared memory model, the EREW PRAM. We show that the upper envelope of n k-intersecting segments can be found in 0(log/sup 1+/spl epsiv//n) time using 0(/spl lambda//sub k+1/(n)/log/sup /spl epsiv//n) processors for any /spl epsiv/>0, where /spl lambda//sub k+2/(n)/sup 1/ is the size of the upper envelope. In particular, for line segments we show the following optimal algorithms: the upper envelope of n line segments can be found in O(log n) time using O(n) processors, and if the line segments are nonintersecting and sorted, the envelope can be found in O(log n) time using O(n/log n) processors. We also show that our methods imply a fast sequential result: the upper envelope of n sorted line segments can be found in O(n log log n) time sequentially, which improves the known lowest upper bound O(n log n).

Article Parallel robust algorithms for constructing strongly convex hulls Share on Authors: Wei Chen Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa, Nagoya 466, Japan Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa, Nagoya 466, JapanView Profile , Koichi Wada Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa, Nagoya 466, Japan Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa, Nagoya 466, JapanView Profile , Kimio Kawaguchi Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa, Nagoya 466, Japan Department of Electrical and Computer Engineering, Nagoya Institute of Technology, Showa, Nagoya 466, JapanView Profile Authors Info & Claims SCG '96: Proceedings of the twelfth annual symposium on Computational geometryMay 1996 Pages 133–140https://doi.org/10.1145/237218.237329Online:01 May 1996Publication History 2citation465DownloadsMetricsTotal Citations2Total Downloads465Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Area and computation time are considered to be important measures with which VLSI circuits are evaluated. In this paper, the area-time complexity for nontrivial n-input m-output Boolean functions, such as a decoder and an encoder, is studied with a model similar to Brent-Kung's model. A lower bound on area-time-product (ATαaα.≥1) for these functions is shown: for example, ATα= ω(2n. nα-l) for an n-input 2V-output decoder, and ATα= ω( n . logα-1n) for an n-input ⌈log n⌉-output encoder. The results shown in this paper are complementary to those by Brent-Kung or Thompson, and are useful for a class of functions of rather simple structures, e.g., a priority encoder, a comparator, and symmetric functions.