Paul Calder, Upasak Weston · 2006
A whole-hearted use of object-oriented techniques to build interactive application interfaces implies that objects should be used for even the smallest components in the interface. This approach often leads to a straightforward implementation that simplifies the programmer’s task, but it can be costly in its use of computer resources. This paper explores the idea of using sharable objects to reduce some of these costs, and it discusses design techniques for making objects sharable. Sharing reduces resource usage in two key ways: it reduces the number of object instances needed to represent application data, and it eliminates some of the structural redundancy inherent in a straightforward use of objects to represent views of hierarchical data. Our approach to making objects sharable is to define dynamic object protocols that reduce the amount of use-specific data that must be stored within object instances.
Cited by 1
Prasad Jayanti, Tushar Chandra, Sam Toueg · Journal of the ACM · 1998
Wait-free implementations of shared objects tolerate the failure of processes, but not the failure of base objects from which they are implemented. We consider the problem of implementing shared objects that tolerate the failure of both processes and base objects. We identify two classes of object failures: responsive and nonresponsive . With responsive failures, a faulty object responds to every operation, but its responses may be incorrect. With nonresponsive failures, a faulty object may also “hang” without responding. In each class, we define crash, omission, and arbitrary modes of failure. We show that all responsive failure modes can be tolerated. More precisely, for all responsive failure modes ℱ, object types T , and t ≥ 0, we show how to implement a shared object of type T which is t -tolerant for ℱ. Such an object remains correct and wait-free even if up to t base objects fail according to ℱ. In contrast to responsive failures, we show that even the most benign non-responsive failure mode cannot be tolerated. We also show that randomization can be used to circumvent this impossibility result. Graceful degradation is a desirable property of fault-tolerant implementations: the implemented object never fails more severely than the base objects it is derived from, even if all the base objects fail. For several failure modes, we show wheter this property can be achieved, and, if so, how.
Cited by 106Open access
Carina Fast, Sue Cobb, Claire O ́Malley et al. · 2000
Cited by 3
Saniya Ben Hassen · 1996
The author has developed a parallel programming model in which partitioned shared objects encapsulate the state and the distribution of data structures in shared-data objects. In this model, the state of an object can be accessed through sequential or parallel operations. This paper describes the object model and partition dependency graphs (PDGs), a mechanism our runtime system uses to prefetch data, reduce access overhead, and increase the overlap between computation and communication during the execution of parallel operations. This mechanism can be applied to statically as well as dynamically allocated objects, i.e., objects for which size and distribution may or may not be known at compile time. This paper illustrates the effectiveness of our prefetching mechanism with two applications: successive overrelaxation (SOR) and fast Fourier transform (FFT). With prefetching, we obtained, respectively, up to 30% and 10% performance improvement.
Cited by 5
2008
We have developed a parallel programming model in which partitioned shared objects encapsulate the state and the distribution of data structures in shared-data objects. In this model, the state of an object can be ac-cessed through sequential or parallel operations. This paper describes the object model and Partition Depen-dency Graphs (PDGs), a mechanism our runtime sys-tem uses to prefetch data, reduce access overhead, and increase the overlap between computation and commu-nication during the execution of parallel operations. This mechanism can be applied to statically as well as dynamically allocated objects, i.e., objects for which size and distribution may or may not be known at compile time. This,paper illustrates the eflectiveness of our prefetching mechanism w&h two applications: Successive OverRelaxation (SOR) and Fast Fourier Transform (FFT). With prefetching, we obtained, re-spectively, up to 30 % and 10 % performance improve-ment. 1
Cited by 0
Koen Langendoen, R.A.F. Bhoedjang, Henri E. Bal · 1996
Cited by 2
Gareth Smith, Gareth Smith, Tom Rodden et al. · 1994
The development and use of multi-user interfaces within CSCW has highlighted the need for users to manage interface configuration and tailoring. Facilities to manage multi-user interfaces tend to be application specific and provide only limited tailorability for purpose built cooperative applications. The structure of applications also prohibits the migration of existing applications to cooperative settings. In this paper we present a multi-user interface toolkit that provides management facilities in a manner that is sympathetic to the migration of existing single-user applications. This is achieved by allowing multi-user interfaces to be derived from a common shared interface constructed from shared interface objects. KEYWORDS Cooperative Interfaces, Interface Toolkits, Interface Coupling. INTRODUCTION The development of applications that support a number of interfaces across a community of users has played a prominent role in CSCW. Different researchers have investigated techniques ...
Cited by 0
Doorn, L. van, Tanenbaum, A.S. · Digital Academic REpository of VU University Amsterdam (Vrije Universiteit Amsterdam) · 1994
Cited by 0
Nan Li, Wojciech Golab · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
The recent commercial release of persistent main memory by Intel has sparked intense interest in recoverable concurrent objects. Such objects maintain state in persistent memory, and can be recovered directly following a system-wide crash failure, as opposed to being painstakingly rebuilt using recovery state saved in slower secondary storage. Specifying and implementing recoverable objects is technically challenging on current generation hardware precisely because the top layers of the memory hierarchy (CPU registers and cache) remain volatile, which causes application threads to lose critical execution state during a failure. For example, a thread that completes an operation on a shared object and then crashes may have difficulty determining whether this operation took effect, and if so, what response it returned. Friedman, Herlihy, Marathe, and Petrank (DISC'17) recently proposed that this difficulty can be alleviated by making the recoverable objects detectable, meaning that during recovery, they can resolve the status of an operation that was interrupted by a failure. In this paper, we formalize this important concept using a detectable sequential specification (DSS), which augments an object’s interface with auxiliary methods that threads use to first declare their need for detectability, and then perform detection if needed after a failure. Our contribution is closely related to the nesting-safe recoverable linearizability (NRL) framework of Attiya, Ben-Baruch, and Hendler (PODC'18), which follows an orthogonal approach based on ordinary sequential specifications combined with a novel correctness condition. Compared to NRL, our DSS-based approach is more portable across different models of distributed computation, compatible with several existing linearizability-like correctness conditions, less reliant on assumptions regarding the system, and more flexible in the sense that it allows applications to request detectability on demand. On the other hand, application code assumes full responsibility for nesting DSS-based objects. As a proof of concept, we demonstrate the DSS in action by presenting a detectable recoverable lock-free queue algorithm and evaluating its performance on a multiprocessor equipped with Intel Optane persistent memory.
Cited by 1Open access
C. Hänle, J. Leiwo, A. S. Tanenbaum · 2007
Designing wide-area distributed object systems is a challenging goal, and security is an important part of the overall architecture. Previous work has focused on developing security frameworks for systems in which objects are scattered all over the Internet, but which have at best sporadic support for the replication of individual objects. Consequently, research addressed the protection of objects, clients and computing resource providers against threats to each other and to external attackers. Recently, a wide-area distributed system based on replicated objects has been proposed. It eases the construction of scalable services since the physical replication of an object is made almost transparent to clients and service developers. Indeed, it blurrs the traditional client/server paradigm, since clients seemlessly become part of the object upon access, and can choose to replicate the object's state. This paper studies the threats arising from the large-scale, wide-area replication of an ...
Cited by 0
Leendert Van, Leendert Van Doorn, Andrew S. Tanenbaum · 1994
This paper discusses a reliable group communication system using active messages to update shared objects. We discuss the model, implementation techniques, and our preliminary performance results. 1. Introduction The performance of parallel programming systems on loosely-coupled machines is mainly limited by the efficiency of its message passing communication architecture. Rendezvous and mail-boxes are the traditional communication mechanisms upon which these systems are built. Unfortunately both mechanisms incur a high latency at the receiver side between arrival and final delivery of the message. An alternative mechanism, active messages [6], reduces this latency by integrating the message data directly into the user-level computation as soon as it arrives. The integration is done by a user specified handler, which is invoked as soon as possible after the hardware receives the message. For interrupt-driven architectures the most obvious design choice is to run the handler directly i...
Cited by 0
Paula Cardoso · 2025
The religious landscape of late medieval Portugal was marked by a call to reform the mendicants that strongly impacted female religious communities and opened ways to more severe approaches to professed life, such as those practiced by the Colettine Clarisses. Bound to a life of enclosure and evangelical poverty, Colettine nuns were simultaneously segregated from their urban communities and in need of their support to survive. Focusing on the promotion of sacred objects and of the figure of Colette of Corbie as strategies of legitimization employed by these convents, this chapter aims to analyse how the establishment of shared devotions between the nuns and their urban communities contributed to the acceptance of these communities and, consequently, attracted and maintained lay support of their convents.
Cited by 0Open access
Andrew S. Tanenbaum, Henri E. Bal, M. Frans Kaashoek · 2002
Building the hardware for a high-performance distributed computer system is a lot easier than building its software. The authors describe a model for programming distributed systems based on abstract data types that can be replicated on all machines that need them. Read operations are done locally, without requiring network traffic. Writes can be done using a reliable broadcast algorithm if the hardware supports broadcasting; otherwise, a point-to-point protocol is used. The authors have built such a system based on the Amoeba microkernel, and implemented a language, Orca, on top of it. For Orca applications that have a high ratio of reads to writes, they measure good speedups on a system with 16 processors.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 16
Joana Campos · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · 2010
As linguagens de programação centradas em objectos, como o Java, conseguem detectar antecipadamente em tempo de Compilação, e assim prevenir, muitos dos erros de tipificação e de inicialização de atributos e variáveis que os programadores inadvertidamente introduzem nos seus códigos. Contudo, estas linguagens são actualmente incapazes de capturar e assinalar erros relacionados com a utilização incorrecta de objectos. Em geral, as linguagens comerciais não dispõem de suporte formal e verificável que garanta que uma instância de uma classe é usada de acordo com a intenção do programador que escreveu essa classe. O protocolo que descreve a leitura de um ficheiro serve de motivação: primeiro o ficheiro deve ser aberto, depois as suas linhas podem ser lidas uma por uma, e, antes de o programa terminar, o ficheiro deve ser fechado. Não havendo qualquer verificação do código cliente a este nível, é inevitável que o protocolo seja quebrado, e que uma tentativa (indevida) de leitura seja efectuada antes de invocada a operação que abre o ficheiro, ou que uma outra esbarre com um ficheiro fechado. Em linguagens como o Java, este tipo de erros só é tarde detectado, quando uma excepção é lançada em tempo de execução. A linguagem de programação MOOL proposta nesta tese representa uma tentativa de formalizar a utilização e o acesso a objectos. Trata-se de uma linguagem baseada em classes, que inclui primitivas disponíveis na maioria dos formalismos de linguagens centradas em objectos. Adicionalmente, a linguagem dispõe de construções sintácticas que permitem ao programador especificar como é que um objecto de uma classe deve ser usado. Através desta especificação, o programador pode (1) definir os métodos disponíveis em função do estado do objecto, e (2) indicar como o objecto pode ser referenciado quando se encontra nesse estado – por uma única referência, tratando-se assim de um objecto linear, ou sem restrições no caso de um objecto que pode ser partilhado por viários clientes. Neste trabalho, a visão abstracta que os clientes têm do estado dos objectos é designada de tipo de utilização da classe (ou class usage type). Ao contrário dos tipos comuns, na linguagem proposta os tipos dos objectos são dinâmico, variando com o seu estado. Gay et al. [38] designam de interface dinâmica a especificação global de método disponíveis numa classe com base no estado do objecto, distinguindo-a da interface estática do Java. Objectos que mudam dinamicamente o conjunto de métodos disponíveis em função do seu estado são também conhecidos na literatura como objectos não uniformes. Nierstrasz [30] foi o primeiro a estudar o comportamento de objectos não uniformes, ou activos, em sistemas concorrentes. A linguagem MOOL oferece ainda um mecanismo de concorrência que permite a criação de threads, além da primitiva sync que permite a sincronização de métodos quando, em objectos partilhados, a comunicação deve ser efectuada em exclusão mútua. A linguagem formal que é apresentada nesta tese é baseada na linguagem proposta por Gay et al. [15], que formaliza uma abordagem designada de tipos de sessão modulares. A teoria dos tipos de sessão foi proposta para a verificação em tempo de Compilação de programas cuja comunicação se processa por canais tipificados. Os tipos de sessão são propostos como forma de impor que as implementações dos canais obedecem às sequências e tipos das mensagens especificados nos protocolos de comunicação. Em geral, os protocolos podem ser expressos por tipos de sessão, independentemente da linguagem de programação em que são integrados. Os tipos de sessão têm sido integrados em viários paradigmas de linguagens de programação: cálculo pi, linguagens funcionais, linguagens centradas em objectos, CORBA, etc. O trabalho sobre tipos de sessão modulares combina, numa linguagem centrada em objectos distribuída, os tipos de sessão e a ideia de disponibilidade dos métodos de uma classe em função do estado do objecto. A modularidade da abordagem resulta de a implementação do tipo de sessão poder ser decomposta pelos viários métodos da classe, contrastando com trabalhos anteriores, no contexto de linguagens centradas em objectos, em que o tipo de sessão é implementado no corpo de um único método. O conceito de tipos de utilização desenvolvido nesta tese foi inspirado nos tipos de sessão modulares, e adaptado a um modelo de comunicação mais simples – a troca de mensagens através de chamadas de métodos. O estilo de programação proposto pretende ser simples e intuitivo, não tendo o programador de lidar com distribuição (a concorrência é efectuada por memória partilhada), mas tirando proveito das propriedades de segurança associadas aos tipos de sessão. As contribuições desta tese materializam-se na formalização da sintaxe, da semântica operacional e do sistema de tipos, que verifica as especificações em tempo de Compilação, e na implementação de um compilador de MOOL, cuja arquitectura também se descreve. No contexto dos tipos de sessão, as contribuições desta tese podem resumir-se nos seguintes pontos: _ Ao contrário de abordagens anteriores, o modelo de comunicação baseia-se exclusivamente na chamada de métodos; _ As classes são anotadas com uma especificação de utilização que estrutura a sequência de métodos que os clientes podem invocar em função do estado do objecto, a qual é enriquecida com qualificadores lin/un que permitem controlar se um objecto é linear, e uma única referência o pode usar, ou se é partilhado, não existindo restrições quanto ao número de clientes; vi _ Ao contrário de abordagens anteriores, os canais partilhados são substituídos pela primitiva de sincronização convencional que permite que certas operações num objecto sejam acedidas sem interferência de outras threads. A tese encontra-se organizada em seis capítulos. Na introdução, o exemplo do leitor de ficheiros é apresentado como motivação dos principais aspectos da linguagem e, em particular, da especificação de tipos de utilização. Segue-se um capítulo onde se apresenta um exemplo mais extenso – o sistema de leilões – que ilustra a introdução de tipos de utilização em protocolos mais complexos. No capítulo da linguagem formal, é descrita a sintaxe, a semântica operacional e o sistema de tipos. Alguns exemplos de derivação de tipos ilustram o funcionamento das regras e as mudanças operadas no tipo dos atributos `a medida que a derivação avança. A prova formal da linguagem MOOL não é apresentada nesta tese, ficando adiada para um trabalho futuro. No entanto, sendo este sistema baseado num sistema de tipos [15] para o qual é apresentada a prova formal por indução, tudo aponta para que não seja difícil provar os resultados também para a linguagem MOOL. No capítulo da implementação, são descritas as tecnologias utilizadas e a arquitectura do compilador. Desenvolvido na linguagem Java, o compilador assenta na framework do SableCC, que gera automaticamente analisadores léxicos e classes que implementam o padrão visitante, o que permitiu reduzir o esforço de implementação ao desenvolvimento da componente semântica, através da extensão destas classes. A arquitectura do compilador distingue duas fases: a fase de análise, onde, com base na árvore abstracta do programa, é construíra a tabela de símbolos e efectuada a verificação de tipos com base num algoritmo de tipificação guiado pelos tipos de utilização, e a fase de síntese, onde o código de um programa MOOL válido é traduzido para uma linguagem intermédia. O resultado desta tradução é convertido em bytecode pela plataforma open source Mono, tendo como alvo a Common Language Runtime (CLR). No capítulo do trabalho relacionado, discute-se o estado da arte em tipos de sessão, focando o contexto das linguagens centradas em objectos, em typestates, uma abordagem com a qual as ideias desta tese apresentam pontos de contacto, e em objectos lineares. Finalmente, na conclusão antecipa-se o trabalho futuro, nomeadamente a apresentação dos resultados da linguagem MOOL e o estudo de técnicas que introduzam alguma flexibilidade na utilização de objectos lineares.
Cited by 7Open access
Polze, A., Malek, M., Humboldt-Universitaet, Berlin (Germany). Inst. fuer Informatik · OpenGrey (Institut de l'Information Scientifique et Technique) · 1995
We present a novel approach to parallel computing in a workstation environment. We introduce Replicated Shared Objects as a programming paradigm which allows encapsulation of communication and synchronization operations within an object's implementation. It also provides an easy-to-use interface to the application programmer. Shared Objects Memory implements our programming paradigm as an object-based, replicated distributed shared memory system on top of network-transparent communication in the Mach operating system. Together with a Remote Execution Service it provides a complete environment for execution of shared-memory parallel programs in workstation clusters. Our system allows for definition and configuration of a virtual parallel machine called 'Shared Objects Net-interconnected Computer' within such a cluster through an easy-to-use graphical interface. Besides a description of our programming paradigm and the 'Shared Objects Net-interconnected Computer' this paper includes promising runtime statistics from early experiments, showing that a cluster of four lowend workstations may have comparable performance with a four-processor shared memory multicomputer such as Sequent Balance. (orig.)
Cited by 0
Philip Homburg, Maarten van Steen, Andrew S. Tanenbaum · Digital Academic REpository of VU University Amsterdam (Vrije Universiteit Amsterdam) · 1996
. Current paradigms for interprocess communication are not sufficient to describe the exchange of information at an adequate level of abstraction. They are either too low-level, or their implementations cannot meet performance requirements. As an alternative, we propose distributed shared objects as a unifying concept. These objects offer user-defined operations on shared state, but allow for efficient implementations through replication and distribution of state. In contrast to other object-based models, these implementation aspects are completely hidden from applications. 1 Introduction Communication can be viewed at different levels of abstraction. At a high level, it appears as an exchange of information between processes. These processes are either contained in a single parallel or distributed application, or may otherwise belong to different applications that need to communicate. At a low level, communication appears as the mere transfer of bits from one address space to another...
Cited by 9Open access
Christopher R. Palmer, Gordon V. Cormack · 1998
A Lock-Free Distributed System is a purely-replicated environment (replication with no central authority) in which updates are performed with no inter-object communication. All replicated copies of an object take on a common state when there are no messages in transit. Such a system is often used for groupware applications and operation transformations are a popular technique in this field. We broaden the scope of operation transformations by using a lock-free concurrency system to specify a distributed spreadsheet. The resulting spreadsheet is highly fault tolerant and the interactive performance is independent of the speed and the quality of the underlying network. To specify the concurrent semantics of the spreadsheet, an abstract data type is defined and a general model of a subset of the operations is proposed. 1 Introduction In the most general sense, an object is a store that has well-defined access methods. That is, an object may assume any of a (potentially infinite) set of v...
Cited by 0
John W. McCormick, Frank Singhoff, Jérôme Hugues · Cambridge University Press eBooks · 2011
In Chapter 3 we introduced the task. The tasks in all of the examples in that chapter were independent. They did not share any resources nor did they communicate with each other. As suggested by the cooking examples of Chapter 1, the solution to most parallel problems requires cooperation among tasks. Such cooperation involves communication, mutual exclusion, and synchronization. Communication is the exchange of data or control signals between processes. Mutual exclusion is a mechanism that prevents two processes from simultaneously using the same resource. Synchronization ensures that multiple processes working on a job complete the steps of that job in the correct order. There are two approaches for communication among processes. In this chapter we look at indirect communication via shared objects. In Chapter 5, we'll look at direct communication via Ada's rendezvous mechanism.
Cited by 0
Leendert van Dorn, Andrew S. Tanenbaum · 1994
This paper discusses a reliable group communication system using active messages to update shared objects. We discuss the model, implementation techniques, and our preliminary performance results.
Cited by 7
Leendert van Dorn, Andrew S. Tanenbaum · 1994
This paper discusses a reliable group communication system using active messages to update shared objects. We discuss the model, implementation techniques, and our preliminary performance results.
Cited by 2Open access