Step semantics for “true” concurrency with recursion

We present a variety of denotational linear time semantics for a language with recursion and true concurrency in a form of synchronous co-operation, which in the literature is known as step semantics. We show that this can be done by a generalization of known results for interleaving semantics. A general method is presented to define semantical operators and denotational semantics in the Smyth powerdomain of streams. With this method, first a naive and then more sophisticated semantics for synchronous co-operation are developed, which include such features as interleaving and synchronization. Then we refine the semantics to deal with a bounded number of processors, subatomic actions, maximal parallelism and a real-time operator. Finally, it is indicated how to apply these ideas to branching-time models, where it becomes possible to analyze deadlock behaviour as well as a form of true concurrency. John-Jules Meyer received his Master's degree in Mathematics in 1979 from the University of Leiden, and his Ph.D. degree in 1985 from the Free University Amsterdam. He is currently a Professor of Theoretical Computer Science, both at the Free University Amsterdam and at the University of Nijmegen. His current research interests include semantics of programming languages and logics for computer science, in particular artifical intelligence. Erik de Vink received the M.S. degree in Mathematics from the University of Amsterdam. He is currently a Junior Researcher at the Department of Mathematics and Computer Science of the Free University Amsterdam. At the moment his main research concerns the semantics of concurrent and logic programming languages.     

Optimal coteries for rings and related networks

Summary Let a distributed system be represented by a graphG=(V, E), whereV is the set of nodes andE is the set of communication links. A coterie is defined as a family,C, of subsets ofV such that any pair of subsets inC has at least one node in common and no subset inC contains any other subset inC. Assuming that each nodev _i V (resp. linke _j E) is operational with probabilityp _i (resp.r _j ), the availability of a coterie is defined as the probability that the operational nodes and links ofG connect all nodes in at least one subset in the coterie. Although it is computationally intractable to find an optimal coterie that maximizes availability for general graphG, we show in this paper that, ifG is a ring, either a singleton coterie or a 3-majority coterie is optimal. Therefore, for any ring, an optimal coterie can be computed in polynomial time. This result is extended to the more general graphs, in which each biconnected component is either an edge or a ring. Toshihide Ibaraki received the B.E., M.E., and Dr. E. degrees from Kyoto University, in 1963, 1965 and 1970, respectively. Since 1969, he has been with the Department of Applied Mathematics and Physics, Kyoto University, except for two and a half years from 1983 to 1985, during which time he was with Department of Computer and Information Sciences, Toyohashi University of Technology. Currently, he is a professor of Kyoto University. He has held a number of visiting appointments with University of Illinois, University of Waterloo, Simon Fraser University, Rutgers University, and others. He is the author of Enumerative Approaches to Combinatorial Optimization, Baltzer AG., a coauthor of Resource Allocation Problems: Algorithmic Approaches, MIT Press, and the author of several books in Japanese, including Algorithms and Data Structures, Shoukohdou. His interest includes algorithms, optimization, computational complexity and their applications. Hiroshi Nagamochi was born in Tokyo, on January 1, 1960. He received the B.A., M.E. and D.E. degrees from Kyoto University, in 1983, in 1985 and in 1988, respectively. From 1988 to 1990, he was with Department of Computer and Information Sciences, Toyohashi University of Technology. Currently, he is an Associate Professor in the Department of Applied Mathematics and Physics at Kyoto University. His research interests include network flow problems and graph connectivity problems. Dr. Nagamochi is a member of the Operations Research Society of Japan and the Information Processing Society. Tsunehiko Kameda received the B.E. and M.E. degrees from the University of Tokyo in 1961 and 1963, respectively, and the Ph.D. degree from Princeton University in 1968. From 1967 to 1980, he was with the Department of Electrical Engineering, University of Waterloo. Since 1981, he has been with Simon Fraser University, Burnaby, British Columbia, Canada, where he is a Professor of Computing Science and is the Director of Computer and Communications Research Laboratory. He has held a number of visiting appointments with Universities of Erlangen-Nürnberg, Bonn, Frankfurt, and Braunschweig, and Gesellschaft für Mathematik und Datenverarbeitung, all in Germany, and also with Kyoto University, Japan. Dr. Kameda is a member of the ACM. He has co-authored three books: Einführung in die Codierungstheorie, Bibliographisches Institut, Distributed Algorithms, Kindai Kagaku-Sha, and A Probabilistic Analysis of Test Response Compaction, IEEE Press. His current research interests include database systems, combinatorial algorithms, distributed computing, ATM networks, and random testing of VLSI circuits.This work was supported in part by Grant-in-Aid from the Ministry of Education, Science and Culture of Japan, and in part by grants from the Natural Sciences and Engineering Research Council of Canada, and the Advanced Systems Institute of British Columbia.     

Using mappings to prove timing properties

Summary A new technique for proving timing properties for timing-based algorithms is described; it is an extension of the mapping techniques previously used in proofs of safety properties for asynchronous concurrent systems. The key to the method is a way of representing a system with timing constraints as an automaton whose state includes predictive timing information. Timing assumptions and timing requirements for the system are both represented in this way. A multi-valued mapping from the assumptions automaton to the requirements automaton is then used to show that the given system satisfies the requirements. One type of mapping is based on a collection of progress functions providing measures of progress toward timing goals. The technique is illustrated with two examples, a simple resource manager and a two-process race system. Nancy A. Lynch received the B.S. degree in mathematics from Brooklyn College, Brooklyn, NY, in 1968, and the Ph.D. degree in mathematics from the Massachusetts Institute of Technology, Cambridge, MA, in 1972. She is presently a professor of computer science and electrical engineering at Massachusetts Institute of Technology. She has also been on the computer science faculty at Georgia Institute of Technology and on the mathematics faculty at Tufts University and the University of Southern California. Her research interests are in distributed and real-time computing and theoretical computer science. In particular, she has worked on formal models and verification methods, on algorithm design and analysis, and on impossibility results. She also likes to hike and ski. Hagit Attiya received the B.Sc. degree in Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the department of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms.This work was supported by ONR contracts N00014-85-K-0168 and N00014-91-J-1046, by NSF grants CCR-8611442 and CCR-8915206, and by DARPA contracts N00014-87-K-0825 and N00014-89-J-1988     

Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection

Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by rounds of the multi-hop network and succeeds with probability 1–. (n is the number of processors,D the diameter and the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains . A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network. Reuven Bar-Yehuda was born in Iran, on July 17th 1951. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1978, 1980, and 1983, respectively. He is currently a Senior Lecturer of Computer Science at the Technion. From 1984 to 1986, he was a visiting assistant professor in the Computer Science Dept. at the Duke Univesity His research interests include computational geometry, VLSI, graph algorithms and distributed algorithms. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science at the Technion. From 1983 to 1986, he was a postdoctoral fellow at MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Alon Itai was born in Scotland, on December 12th 1946. Received B.Sc. in Mathematics from the Hebrew University in Jerusalem in 1969. M.Sc., and Ph.D. in Computer Science from the Weizmann Institute of Science, Rehovot, Israel in 1971 and 1976. He is currently an Associate Professor of Computer Science at the Technion. His research interests include randomized and distributed algorithms, computational learning theory and performance evaluation.The second author was partially supported by grant No. 86-00301 from the United States—Israel Bi-national Science Foundation BSF), Jerusalem, Israel.     

The CPR Model for Summarizing Video

Most past work on video summarization has been based on selecting key frames from videos. We propose a model of video summarization based on three important parameters: Priority (of frames), Continuity (of the summary), and non-Repetition (of the summary). In short, a summary must include high priority frames and must be continuous and non-repetitive. An optimal summary is one that maximizes an objective function based on these three parameters. We show examples of how CPR parameters can be computed and provide algorithms to find optimal summaries based on the CPR approach. Finally, we briefly report on the performance of these algorithms.Marat Fayzullin has received his PhD degree in Computer Science from the University of Maryland, College Park, in 2004. He has done research in Distributed Simulation Environments, Multimedia Database Algebras, and Automated Content Summarization. His topics of interest also include Mobile Agent Networks and Reasoning with Semantic Networks.V.S. Subrahmanian received his Ph.D. in Computer Science from Syracuse University in 1989. Since then, he has been on the faculty of the Computer Science Department at the University of Maryland, College Park, where he currently holds the rank of Professor. He also serves as Director of the University of Marylands Institute for Advanced Computer Studies (UMIACS) established by the State of Maryland in the mid-1980s to pursue interdisciplinary research involving IT. He received the NSF Young Investigator Award in 1993 and the Distinguished Young Scientist Award from the Maryland Academy of Science/Maryland Science Center in 1997. Prof. Subrahmanian is recognized for his work on nonmonotonic and probabilistic logics, inconsistency management in databases, database models views and inference, rule bases, heterogeneous databases, multimedia databases, and probabilistic databases. More recently, he has developed techniques to agentize legacy software, allowing multiple software modules to dynamically collaborate with each other to solve complex problems. He has edited two books, one on nonmonotonic reasoning (MIT Press) and one on multimedia databases (Springer). He has co-authored an advanced database textbook (Morgan Kaufman, 1997) and a book on heterogeneous software agents. He is the sole author of the best known textbook on multimedia databases (Morgan Kaufmann)—a second edition of this book is under preparation. Prof. Subrahmanian has given invited talks at numerous national and international conferences—in addition, he has served on numerous conference and funding panels, as well as on the program committees of numerous conferences. He has also chaired several conferences. Prof. Subrahmanian is or has previously been on the editorial board of IEEE Transactions on Knowledge and Data Engineering, Artificial Intelligence Communications, Multimedia Tools and Applications, Journal of Logic Programming, Annals of Mathematics and Artificial Intelligence, Distributed and Parallel Database Journal, and Theory and Practice of Logic Programming.Prof. Subrahmanian has served on DARPAs (Defense Advanced Research Projects Agency) Executive Advisory Council on Advanced Logistics and as an ad-hoc member of the US Air Force Science Advisory Board (2001).Antonio Picariello received the Laurea degree in Electronics Engineering from the University of Napoli, Italy, in 1991. In 1993 he joined the Istituto Ricerca Sui Sistimi Informatici Paralleli, The National Research Council, Napoli, Italy. He received a Ph.D. degree in Computer Science and Engineering in 1998 from the University of Naples Federico II. In 1999, he joined the Dipartimento di Informatica e Sistemistica, University of Napoli Federico II, Italy, and is currently an Associate Professor of Data Base. He has been active in the field of Computer Vision, Medical Image Processing and Pattern Recognition, Object-Oriented models for image processing, Multimedia Data Base and Information Retrieval. His current research interests lie in Knowledge Extraction and Management, Multimedia Integration and Image and Video databases. He is a member of the International Association of Pattern Recognition.Maria Luisa Sapino has got her master degree and Ph.D. in Computer Science at the University of Torino, where shes currently Associate Professor. She initially worked in the area of logic programming and artificial intelligence, specifically interested in the semantics of negation in logic programming, and in the abductive extensions of logic programs. Her current research interests include heterogeneous and multimedia databases, in particular similarity based information retrieval, and modeling and querying multimedia presentations. She has been serving as a reviewer for several international conferences and journals.     

Naming symmetric processes using shared variables

Summary Implementations of inter-process communication and synchronization in distributed systems usually rely on the existence of unique ids for the processes. We consider the problem of generating such ids for identical processes in a shared-variable system. A randomized protocol that assigns distinct ids to the processes within an expected polynomial number of rounds using a polynomial number of boolean atomic variables is presented. Ömer Eeciolu obtained his Ph.D. degree in mathematics from the University of California, San Diego in 1984. At present he is an Associate Professor in the Computer Science department of the University of California, Santa Barbara, where he has been on the faculty since 1985. His principal areas of research are parallel algorithms, bijective and enumerative combinatorics, and combinatorial algorithms. His current interest in parallel algorithms involve approximation and numerical techniques on distributed memory systems while his combinatorial interests center around computational geometry, bijective methods, and ranking algorithms for combinatorial structures. Ambuj K. Singh is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. He received a Ph.D. in Computer Science from the University of Texas at Austin in 1989, an M.S. in Computer Science from Iowa State University in 1984, and a B. Tech. from the Indian Institute of Technology at Kharagpur in 1982. His research interests are in the areas of adaptive resource allocation, concurrent program development, and distributed shared memory.Work supported in part by NSF grants CCR-9008628 and CCR-9223094     

André Gide''s collection of faits divers

André Gide's collection offaits divers spans a period of fifty years and includes more than 650 documents. A database analysis offers an efficient means of handling such extensive material. Our goal is to trace statistically this author's varied interests as they evolved throughout his career.Elizabeth R. Jackson is Professor Emeritus from San Diego State University. She has published works on French Poetry, Proust and Gide. Her most recent books include an annotated bilingual edition of Meidosems by Henri Michaux and a book published for the University of Bari in Italy, by Schena-Nizet, Secrets Observateurs ...: la poésie d'André Chénier.     

Clock synchronization and the power of broadcasting

Summary We investigate the power of a broadcast mechanism in a distributed network. We do so by considering the problem of synchronizing clocks in an errorfree network, under the assumption that there is no upper bound on message transmission time, but that broadcast messages are guaranteed to be received within an interval of size , for some fixed constant . This is intended to be an idealization of what happens in multiple access networks, such as the Ethernet. We then consider tradeoffs between the type and number of broadcasts, and the tightness of synchronization. Our results include (1) matching upper and lower bounds of (1+1/K) on the precision of clock synchronization attainable forn3 process usingK (n–1)-casts, 3Kn, (2) matching upper and lower bounds of (1+1/n) on the precision of clock synchronization attainable forn3 processes using an arbitrary number of (n–1)-casts, and (3) matching upper and lower bounds of (1+n–2/n) on the precision attainable using 2-casting. Joseph Y. Halpern received a B.Sc. in mathematics from the University of Toronto in 1975, and a Ph.D. in mathematics from Harvard University in 1981. In between, he spent two years as the head of the Mathematics Department at Bawku Secondary School in Ghara. After a year as a visiting scientist at MIT, he joined IBM in 1982, where he is currently a research staff member, as well as being a consulting professor at Stanford University. He was manager of the mathematics and related computer sience department at IBM from 1987–1989. He was program chairman and organizer of the first conference on Theoretical Aspects of Reasoning About Knowledge in 1986, program chairman of the 1986 ACM Symposium on Principles of Distributed Computing and of the 1991 ACM Symposium on Theory of Computing. He was recipent (together with Ron Fagin) of the MIT Publisher's Prize for best paper at the 1985 International Joint Conference on Artificial Intelligence and again winner of the Publisher's Prize at the 1989 International Joint Conference on Artificial Intelligence. Ichiro Suzuki is an Associate Professor of Computer Science at the University of Wisconsin-Milwaukee. He received a D.E. degree in information and computer sciences from Osaka University, Japan, in 1983. His major research interests are distributed systems and computational geometry.This author was supported in part by the National Science Foundation under grant CCR-9004346     

Implementation of hierarchical F-channels for high-performance distributed computing

Summary High performance distributed computing systems require high performance communication systems.F-channels andHierarchical F-channels address this need by permitting a high level of concurrency like non-FIFO channels while retaining the simplicity of FIFO channels critical to the design and proof of many distributed algorithms. In this paper, we present counter-based implementations for F-channels and Hierarchical F-channels using message augmentation-appending control information to a message. These implementations guarantee that no messages are unnecessarily delayed at the receiving end. Keith Shafer received the B.A. degree in computer science and mathematics in 1986 from Mount Vernon Nazarene College, Mount Vernon, Ohio, USA, and the M.S. and Ph.D. degrees in computer science from The Ohio State University, Columbus, Ohio, USA, in 1988 and 1992, respectively. He is currently a Senior Research Scientist at OCLC Online Computer Library Center Inco, Dublin, OH, USA. His research interests include tools for comparing logical channels and methods for automatically constructing corpus grammars from tagged documents as an aid for database preparation and document conversion. Dr. Shafer is a member of the IEEE Computer Society. Mohan Ahuja received the M.A. degree in 1983 and the Ph.D. degree in 1985, both in computer science, from the University of Texas at Austin. He is currently with Department of Computer Science and Engineering, Univ. of California, San Diego. His recent research contributions include Global Flushing, message receipt in Receive-Phases, Incremental Publication of a Partial Order, Design of Highways (a high-performance distributed programming system) and — in collaboration with others — Passive-space and Time View, Performance evaluation of F-Channels, and Units of Computation in Fault-Tolerant Distributed Systems. His current research interests are in high-performance distributed communication and computing architectures, building high-performance systems, distributed operating systems, distributed algorithms, fault tolerance, and performance evaluation.Parts of this paper appeared in two conference papers, (1) Distributed Modeling and Implementation of High Performance Communication Architectures, in proceedings of the Thirteenth IEEE International Conference on Distributed Computing Systems, papes 56–65, 1993 and (2) Process-Channel_agem-Process model of asynchronous distributed communication, in proceedings of the Twelfth IEEE International Conference on Distributed Computing Systems, pages 4–11, 1992     

Test Resource Partitioning Based on Efficient Response Compaction for Test Time and Tester Channels Reduction

This paper presents a test resource partitioning technique based on an efficient response compaction design called quotient compactor(q-Compactor). Because q-Compactor is a single-output compactor, high compaction ratios can be obtained even for chips with a small number of outputs. Some theorems for the design of q-Compactor are presented to achieve full diagnostic ability, minimize error cancellation and handle unknown bits in the outputs of the circuit under test (CUT). The q-Compactor can also be moved to the load-board, so as to compact the output response of the CUT even during functional testing. Therefore, the number of tester channels required to test the chip is significantly reduced. The experimental results on the ISCAS ‘89 benchmark circuits and an MPEG 2 decoder SoC show that the proposed compactionscheme is very efficient.     

Directional derivatives of the maximum function

Directional differentiability of the function (x) = sup{f(x, u), u U} is proved for a class of smooth functions f. The result is applied to study the directional differentiability of the function (x) = sup{f(x, y), y F(x)}, where F is a multivalued mapping.Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 171–173, March–April, 1992.     

The construction of self-synchronizing finite state protocols

A technique is presented for constructing a finite state protocol from an originally given finite state specification of one process. We present three constructions, showing that they each provide send-receive symmetric solutions which are selfsynchronizing. Two lemmas are proved that provide insight into the types of interactions that arise in these types of finite state protocols. In essence we show that interactions occur between the processes only through isomorphic transitions and that during any interaction between the processes at most one of the two FIFO queues of messages is nonempty.Raymond E. Miller has been Director and Professor of the School of Information and Computer Science at the Georgia Institute of Technology since 1980. Prior to that he was employed by IBM for over thirty years, most of this time as a Research Staff Member at the IBM Research Center in Yorktown Heights, N.Y., where he held a number of technical management positions. He received a B.S. in Mechanical Engineering from the University of Wisconsin, Madison, and a B.S. in Electrical Engineering, M.S. in Mathematics, and PhD in Electrical Engineering, all from the University of Illinois, Urbana. His research areas of interest include theory of computation, machine organization, parallel computation, and communication protocols. He has written over sixty papers, authored a two volume book on switching theory, served as editor for a book on computer complexity, and is editor of a book series of foundations of computer science. He is a Fellow of the IEEE, a member of ACM and AAAS and has been active in numerous ACM capacities including being a member of the ACM Council for six years, an ACM National Lecturer for 1982–83, and a member of the AFIPS Board of Directors for four years. He is a member of the Computer Science Board, and was a member of the NSF Advisory Committee for Computer Research from 1982 to 1985, serving as Chairman for 1983–84. He has taught in a visiting or part time capacity at numerous institutions including Cal Tech, New York University, Yale, University of California at Berkeley and the Polytechnic Institute of New York.This work was partially supported through a contract with GTE Laboratories     

Algebraic and functional specification of an interactive serializable database interface

Summary A formal functional specification of a serializable interface for an interactive database is given and refined into two different versions with distinct strategies for solving read/write conflicts. The formalization is based on techniques of algebraic specification for defining the basic data structures and functional system specification by streams and stream processing functions for defining the properties concerning interaction. It is especially demonstrated how different specification techniques can be used side by side. Manfred Broy finished his studies with the Diplom in Mathematics and Computer Science at the Technical University of Munich. Till 1983 he was research and teaching assistant at the Institut für Informatik and the Sonderforschungsbereich 49 Programmiertechnik. At the Technical University of Munich he also did his Ph.D. (in February 1980 with the subject: Transformation parallel ablaufender Programme) and qualified as an university lecturer (in 1982 with the subject: A Theory for Nondeterminism, Parallelism, Communication and Concurrency). In April 1983 he became a Full Professor for Computer Science at the Faculty of Mathematics and Computer Science at the University of Passau. Since October 1989 he has been Full Professor for Computer Science at the Technical University of Munich. His fields of interests are: Programming languages, program development, programming methodology and distributed systems.This work was supported by the DFG Project Transformation paralleler Programme and by the Sonderforschungsbereich 342 Werkzeuge und Methoden für die Nutzung paralleler Architekturen     

Counting networks with arbitrary fan-out

Summary It is shown that an acyclic smoothing network (and hence counting network) with fan-outn cannot be constructed from balancers of fan-outb ₁,...,b _k , if there exists a prime factorp ofn, such thatp does not divideb _i , for alli, 1ik. This holds regardless of the depth, fan-in or size of the network, as long as they are finite. On the positive side, a simple construction ofcyclic counting networks with fan-outn, for arbitraryn, is presented. An acyclic counting network with fan-in and fan-outp2 ^k , for any integerk0, is constructed out of 2-balancers andp-balancers. Eran Aharonson received the B.A. and M.Sc. degrees in Computer Science from the Technion, Israel Institute of Technology (Haifa, Israel) in 1989 and 1992, respectively. He is currently vice president for research and development at ART-Advanced Recognition Technolgies Ltd., a company dedicated to handwriting and voice recognition. His general research interests are distributed computation, theoretical computer science and pattern recognition. Hagit Attiya received the B.Sc. degree in Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the department of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms.A preliminary version of this paper appears in proceedings of the3rd Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992, pp. 104–113. This research was supported by Technion V.P.R.-B. and G. Greenberg Research Fund (Ottawa)Supported by Rashi Enterprise graduate fellowship     

Change Detection in Overhead Imagery Using Neural Networks

Identifying interesting changes from a sequence of overhead imagery—as opposed to clutter, lighting/seasonal changes, etc.—has been a problem for some time. Recent advances in data mining have greatly increased the size of datasets that can be attacked with pattern discovery methods. This paper presents a technique for using predictive modeling to identify unusual changes in images. Neural networks are trained to predict before and after pixel values for a sequence of images. These networks are then used to predict expected values for the same images used in training. Substantial differences between the expected and actual values represent an unusual change. Results are presented on both multispectral and panchromatic imagery.     

Nonblockability of Switches with the Cayley Graph Structure for Serial Transfer of Data Blocks. Generalized Hypercubes and Multidimensional Grids

A general method of conflictless arbitrary permutation of large data elements that can be divided into a multitude of smaller data blocks was considered for switches structured as the Cayley graphs. The method was specified for arbitrary permutations in the generalized hypercubes and multidimensional grids, and their characteristics were considered.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.