Radio remains a pervasive medium for mass information dissemination, with AM/FM stations reaching more Americans than either smartphone-based social networking or live television.Increasingly, radio broadcasts are also streamed online and accessed over the Internet.We present WavePulse, a framework that records, documents, and analyzes radio content in real-time.While our framework is generally applicable, we showcase the efficacy of WavePulse in a collaborative project with a team of political scientists focusing on the 2024 Presidential Election.We use WavePulse to monitor livestreams of 396 news radio stations over a period of three months, processing close to 500,000 hours of audio streams.These streams were converted into time-stamped, diarized transcripts and analyzed to answer key political science questions at both the national and state levels.Our analysis revealed how local issues interacted with national trends, providing insights into information flow.Our results demonstrate WavePulse's efficacy in capturing and analyzing content from radio livestreams sourced from the Web.Code and dataset can be accessed at https://wave-pulse.io

The spread of online misinformation threatens public health, democracy, and the broader society. While professional fact-checkers form the first line of defense by fact-checking popular false claims, they do not engage directly in conversations with misinformation spreaders. On the other hand, non-expert ordinary users act as eyes-on-the-ground who proactively counter misinformation – recent research has shown that 96% counter-misinformation responses are made by ordinary users. However, research also found that 2/3 times, these responses are rude and lack evidence. This work seeks to create a counter-misinformation response generation model to empower users to effectively correct misinformation. This objective is challenging due to the absence of datasets containing ground-truth of ideal counter-misinformation responses, and the lack of models that can generate responses backed by communication theories. In this work, we create two novel datasets of misinformation and counter-misinformation response pairs from in-the-wild social media and crowdsourcing from college-educated students. We annotate the collected data to distinguish poor from ideal responses that are factual, polite, and refute misinformation. We propose MisinfoCorrect, a reinforcement learning-based framework that learns to generate counter-misinformation responses for an input misinformation post. The model rewards the generator to increase the politeness, factuality, and refutation attitude while retaining text fluency and relevancy. Quantitative and qualitative evaluation shows that our model outperforms several baselines by generating high-quality counter-responses. This work illustrates the promise of generative text models for social good – here, to help create a safe and reliable information ecosystem. The code and data is accessible on https://github.com/claws-lab/MisinfoCorrect.

Malware analysis aims to understand how malicious software carries out actions necessary for a successful attack and identify the possible impacts of the attack. While there has been substantial research focused on malware analysis and it is an important tool for practitioners in industry, the overall malware analysis process used by practitioners has not been studied. As a result, an understanding of common malware analysis workflows and their goals is lacking. A better understanding of these workflows could help identify new research directions that are impactful in practice. In order to better understand malware analysis processes, we present the results of a user study with 21 professional malware analysts with diverse backgrounds who work at 18 different companies. The study focuses on answering three research questions: (1) What are the different objectives of malware analysts in practice?, (2) What comprises a typical professional malware analyst workflow, and (3) When analysts decide to conduct dynamic analysis, what factors do they consider when setting up a dynamic analysis system? Based on participant responses, we propose a taxonomy of malware analysts and identify five common analysis workflows. We also identify challenges that analysts face during the different stages of their workflow. From the results of the study, we propose two potential directions for future research, informed by challenges described by the participants. Finally, we recommend guidelines for developers of malware analysis tools to consider in order to improve the usability of such tools.

New security concerns arise due to the growing popularity of voice assistants (VA) in home and enterprise networks. We explore how malware infected computers can encode sensitive data into audio and leverage nearby VAs to exfiltrate it. Such low cost attacks can be launched remotely, at scale, and can bypass network defenses. By using Dual-Tone Multi-Frequency tones to encode data into audio that is played over ordinary computer speakers, modest amounts of data (e.g., a kilobyte) can be transmitted with a phone call lasting a few minutes. This can be done while making the audio nearly inaudible for most people. With the help of a prototype built by us, we experimentally assess the impact of several factors that impact data transfer rates and transmission accuracy achieved by such attacks. Our results show that voice assistants in the vicinity of computers can pose new threats to data stored on them.

What should a malicious user write next to fool a detection model? Identifying malicious users is critical to ensure the safety and integrity of internet platforms. Several deep learning based detection models have been created. However, malicious users can evade deep detection models by manipulating their behavior, rendering these models of little use. The vulnerability of such deep detection models against adversarial attacks is unknown. Here we create a novel adversarial attack model against deep user sequence embedding-based classification models, which use the sequence of user posts to generate user embeddings and detect malicious users. In the attack, the adversary generates a new post to fool the classifier. We propose a novel end-to-end Personalized Text Generation Attack model, called PETGEN, that simultaneously reduces the efficacy of the detection model and generates posts that have several key desirable properties. Specifically, PETGEN generates posts that are personalized to the user's writing style, have knowledge about a given target context, are aware of the user's historical posts on the target context, and encapsulate the user's recent topical interests. We conduct extensive experiments on two real-world datasets (Yelp and Wikipedia, both with ground-truth of malicious users) to show that PETGEN significantly reduces the performance of popular deep user sequence embedding-based classification models. PETGEN outperforms five attack baselines in terms of text quality and attack efficacy in both white-box and black-box classifier settings. Overall, this work paves the path towards the next generation of adversary-aware sequence classification models.

Spam phone calls have been rapidly growing from nuisance to an increasingly effective scam delivery tool. To counter this increasingly successful attack vector, a number of commercial smartphone apps that promise to block spam phone calls have appeared on app stores, and are now used by hundreds of thousands or even millions of users. However, following a business model similar to some online social network services, these apps often collect call records or other potentially sensitive information from users’ phones with little or no formal privacy guarantees.

Fact checking by professionals is viewed as a vital defense in the fight against misinformation. While fact checking is important and its impact has been significant, fact checks could have limited visibility and may not reach the intended audience, such as those deeply embedded in polarized communities. Concerned citizens (i.e., the crowd), who are users of the platforms where misinformation appears, can play a crucial role in disseminating fact-checking information and in countering the spread of misinformation. To explore if this is the case, we conduct a data-driven study of misinformation on the Twitter platform, focusing on tweets related to the COVID-19 pandemic, analyzing the spread of misinformation, professional fact checks, and the crowds response to popular misleading claims about COVID-19.In this work, we curate a dataset of false claims and statements that seek to challenge or refute them. We train a classifier to create a novel dataset of 155,468 COVID-19-related tweets, containing 33,237 false claims and 33,413 refuting arguments. Our findings show that professional fact-checking tweets have limited volume and reach. In contrast, we observe that the surge in misinformation tweets results in a quick response and a corresponding increase in tweets that refute such misinformation. More importantly, we find contrasting differences in the way the crowd refutes tweets, some tweets appear to be opinions, while others contain concrete evidence, such as a link to a reputed source. Our work provides insights into how misinformation is organically countered in social platforms by some of their users and the role they play in amplifying professional fact checks. These insights could lead to development of tools and mechanisms that can empower concerned citizens in combating misinformation. The code and data can be found in this link.1

The telephony channel has become an attractive target for cyber criminals, who are using it to craft a variety of attacks. In addition to delivering voice and messaging spam, this channel is also being used to lure victims into calling phone numbers that are controlled by the attackers. One way this is done is by aggressively advertising phone numbers on social media (e.g., Twitter). This form of spam is then monetized over the telephony channel, via messages/calls made by victims. We refer to this type of attacks as outgoing phone communication (OPC) attacks.

Technical Support Scams (TSS), which combine online abuse with social engineering over the phone channel, have persisted despite several law enforcement actions. Although recent research has provided important insights into TSS, these scams have now evolved to exploit ubiquitously used online services such as search and sponsored advertisements served in response to search queries. We use a data-driven approach to understand search-and-ad abuse by TSS to gain visibility into the online infrastructure that facilitates it. By carefully formulating tech support queries with multiple search engines, we collect data about both the support infrastructure and the websites to which TSS victims are directed when they search online for tech support resources. We augment this with a DNS-based amplification technique to further enhance visibility into this abuse infrastructure. By analyzing the collected data, we provide new insights into search-and-ad abuse by TSS and reinforce some of the findings of earlier research. Further, we demonstrate that tech support scammers are (1) successful in getting major as well as custom search engines to return links to websites controlled by them, and (2) they are able to get ad networks to serve malicious advertisements that lead to scam pages. Our study period of approximately eight months uncovered over 9,000 TSS domains, of both passive and aggressive types, with minimal overlap between sets that are reached via organic search results and sponsored ads. Also, we found over 2,400 support domains which aid the TSS domains in manipulating organic search results. Moreover, to our surprise, we found very little overlap with domains that are reached via abuse of domain parking and URL-shortening services which was investigated previously. Thus, investigation of search-and-ad abuse provides new insights into TSS tactics and helps detect previously unknown abuse infrastructure that facilitates these scams.

Telephone networks first appeared more than a hundred years ago, long before transistors were invented. They, therefore, form the oldest large scale network that has grown to touch over 7 billion people. Telephony is now merging many complex technologies and because numerous services enabled by these technologies can be monetized, telephony attracts a lot of fraud. In 2015, a telecom fraud association study estimated that the loss of revenue due to global telecom fraud was worth 38 billion US dollars per year. Because of the convergence of telephony with the Internet, fraud in telephony networks can also have a negative impact on security of online services. However, there is little academic work on this topic, in part because of the complexity of such networks and their closed nature. This paper aims to systematically explore fraud in telephony networks. Our taxonomy differentiates the root causes, the vulnerabilities, the exploitation techniques, the fraud types and finally the way fraud benefits fraudsters. We present an overview of each of these and use CAller NAMe (CNAM) revenue share fraud as a concrete example to illustrate how our taxonomy helps in better understanding this fraud and to mitigate it.

Over the past decade, the number of mobile phones has increased dramatically, overtaking the world population in October 2014. In developing countries like India and China, mobile subscribers outnumber traditional landline users and account for over 90% of the active population. At the same time, convergence of telephony with the Internet with technologies like VoIP makes it possible to reach a large number of telephone users at a low or no cost via voice calls or SMS (short message service) messages. As a consequence, cybercriminals are abusing the telephony channel to launch attacks, e.g., scams that offer fraudulent services and voice-based phishing or vishing, that have previously relied on the Internet. In this paper, we introduce and deploy the first mobile phone honeypot called MobiPot that allow us to collect fraudulent calls and SMS messages. We implement multiple ways of advertising mobile numbers (honeycards) on MobiPot to investigate how fraudsters collect phone numbers that are targeted by them. During a period of over seven months, MobiPot collected over two thousand voice calls and SMS messages, and we confirmed that over half of them were unsolicited. We found that seeding honeycards enables us to discover attacks on the mobile phone numbers which were not known before.

Recent convergence of telephony with the Internet offers malicious actors the ability to craft cross-channel attacks that leverage both telephony and Internet resources. Bulk messaging services can be used to send unsolicited SMS messages to phone numbers. While the long-term properties of email spam tactics have been extensively studied, such behavior for SMS spam is not well understood. In this paper, we discuss a novel SMS abuse attribution system called CHURN. The proposed system is able to collect data about large SMS abuse campaigns and analyze their passive DNS records and supporting website properties. We used CHURN to systematically conduct attribution around the domain names and IP addresses used in such SMS spam operations over a five year time period. Using CHURN, we were able to make the following observations about SMS spam campaigns: (1) only 1 % of SMS abuse domains ever appeared in public domain blacklists and more than 94 % of the blacklisted domain names did not appear in such public blacklists for several weeks or even months after they were first reported in abuse complaints, (2) more than 40 % of the SMS spam domains were active for over 100 days, and (3) the infrastructure that supports the abuse is surprisingly stable. That is, the same SMS spam domain names were used for several weeks and the IP infrastructure that supports these campaigns can be identified in a few networks and a small number of IPs, for several months of abusive activities. Through this study, we aim to increase the situational awareness around SMS spam abuse, by studying this phenomenon over a period of five years. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Mobile applications running on devices such as smart phones and tablets will be increasingly used to provide convenient access to health information to health professionals and patients. Also, patients will use these devices to transmit health information captured by sensing devices in settings like the home to remote repositories. As mobile devices become targets of security threats, we must address the problem of protecting sensitive health information on them. We explore key threats to data on mobile devices and develop a security framework that can help protect it against such threats. We implemented this framework in the Android operating system and augmented it with user consent detection to enhance user awareness and control over the use of health information.

The security guarantees provided by SSL/TLS depend on the correct authentication of servers through certificates signed by a trusted authority. However, as recent incidents have demonstrated, trust in these authorities is not well placed. Increasingly, certificate authorities (by coercion or compromise) have been creating forged certificates for a range of adversaries, allowing seemingly secure communications to be intercepted via man-in-the-middle (MITM) attacks. A variety of solutions have been proposed, but their complexity and deployment costs have hindered their adoption. In this paper, we propose Direct Validation of Certificates (DVCert), a novel protocol that, instead of relying on third-parties for certificate validation, allows domains to directly and securely vouch for their certificates using previously established user authentication credentials. By relying on a robust cryptographic construction, this relatively simple means of enhancing server identity validation is not only efficient and comparatively easy to deploy, but it also solves other limitations of third-party solutions. Our extensive experimental analysis in both desktop and mobile platforms shows that DVCert transactions require little computation time on the server (e.g., less than 1 ms) and are unlikely to degrade server performance or user experience. In short, we provide a robust and practical mechanism to enhance server authentication and protect web applications from MITM attacks against SSL/TLS. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

HTTP cookies are the de facto mechanism for session authentication in Web applications. However, their inherent security weaknesses allow attacks against the integrity of Web sessions. HTTPS is often recommended to protect cookies, but deploying full HTTPS support can be challenging due to performance and financial concerns, especially for highly distributed applications. Moreover, cookies can be exposed in a variety of ways even when HTTPS is enabled. In this article, we propose one-time cookies (OTC), a more robust alternative for session authentication. OTC prevents attacks such as session hijacking by signing each user request with a session secret securely stored in the browser. Unlike other proposed solutions, OTC does not require expensive state synchronization in the Web application, making it easily deployable in highly distributed systems. We implemented OTC as a plug-in for the popular WordPress platform and as an extension for Firefox and Firefox for mobile browsers. Our extensive experimental analysis shows that OTC introduces a latency of less than 6 ms when compared to cookies—a negligible overhead for most Web applications. Moreover, we show that OTC can be combined with HTTPS to effectively add another layer of security to Web applications. In so doing, we demonstrate that one-time cookies can significantly improve the security of Web applications with minimal impact on performance and scalability.

The performance of SIP proxies is critical for the robust operation of many applications. However, the use of even light-weight authentication schemes can significantly degrade throughput in these systems. In particular, systems in which multiple proxies share a remote authentication database can experience reduced performance due to latency. In this paper, we investigate how the application of parallel execution and batching can be used to maximize throughput while carefully balancing demands for bandwidth and call failure rates. Through the use of a modified version of OpenSER, a high-performance SIP proxy, we demonstrate that the traditional recommendation of simply launching a large number of parallel processes not only incurs substantial overhead and increases dropped calls, but can actually decrease call throughput. An alternative technique that we implement, request batching, similarly fails to achieve high proxy throughput. Through a carefully selected mix of batching and parallelization, we reduce the bandwidth required to maximize authenticated signaling throughput by the proxy by more than 75 percent. This mix also keeps the call loss rates below 1 percent at peak performance. In addition, we demonstrate that the delay introduced by batching is acceptable for VoIP applications. As a result, our technique significantly reduce the cost and increase the throughput of authentication for large-scale networks supporting SIP applications.

Multi-core architectures are commonly used for network applications because the workload is highly parallelizable. Packet scheduling is a critical performance component of these applications and significantly impacts how well they scale. Deep packet inspection (DPI) applications are more complex than most network applications. This makes packet scheduling more difficult, but it can have a larger impact on performance. Also, packet latency and ordering requirements differ depending on whether the DPI application is deployed inline. Therefore, different packet scheduling tradeoffs can be made based on the deployment.

The recent diversification of telephony infrastructure allows users to communicate through landlines, mobile phones and VoIP phones. However, call metadata such as Caller-ID is either not transferred or transferred without verification across these networks, allowing attackers to maliciously alter it. In this paper, we develop PinDr0p, a mechanism to assist users in determining call provenance - the source and the path taken by a call. Our techniques detect and measure single-ended audio features to identify all of the applied voice codecs, calculate packet loss and noise profiles, while remaining agnostic to characteristics of the speaker's voice (as this may legitimately change when interacting with a large organization). In the absence of verifiable call metadata, these features in combination with machine learning allow us to determine the traversal of a call through as many as three different providers (e.g., cellular, then VoIP, then PSTN and all combinations and subsets thereof) with 91.6% accuracy. Moreover, we show that once we identify and characterize the networks traversed, we can create detailed fingerprints for a call source. Using these fingerprints we show that we are able to distinguish between calls made using specific PSTN, cellular, Vonage, Skype and other hard and soft phones from locations across the world with over 90% accuracy. In so doing, we provide a first step in accurately determining the provenance of a call.

Protecting shared sensitive information is a key requirement for today's distributed applications. Our research uses virtualization technologies to create and maintain trusted data paths across distributed machines, for the services being run and their information exchanges. For trusted data paths, runtime protection methods control what data is visible to which distributed services operating on it, guided by online monitoring that determines the levels of trust inherent in the paths' machines, services, and service actions. This paper presents a key functional element of trusted data paths, which is the ProtectIT interception mechanism for controlling the data exchanges between the different virtual machines running trusted services. ProtectIT can be applied to any communication and/or I/O performed by virtual machines, and because ProtectIT does not require application, middleware, or operating system modifications, it can be used to construct trusted data paths without the knowledge or consent of such entities. Further, since ProtectIT operates in virtual machines isolated from those used by applications, it is not subject to the attacks faced by services exposed to the open Internet. ProtectIT's functionality consists of dynamic protection rules represented as data filters applied to virtual machines' communications. Examples presented in this paper include email services for which ProtectIT's filters control data visibility to mail servers and clients, and unsecured virtual machine communications morphed into secure ones via ProtectIT-based message interception.

A growing class of applications, including VoIP, IM and presence, are enabled by the session initiation protocol (SIP). Requests in SIP typically traverse through multiple proxies. The availability of multiple proxies offers the flexibility to distribute proxy functionality across several nodes. In particular, after experimentally demonstrating that the resource consumption of maintaining state is significant, we define the problem of state distribution across multiple nodes when the goal is to increase overall call throughput. We first formulate this as an optimization problem and then derive a distributed algorithm from it. This distributed algorithm leads to the design and evaluation of SERvartuka, a more scalable SIP server that dynamically determines the number of SIP requests for which the server is stateful while delegating state maintenance for the remainder of the requests to a server further downstream. This design is in contrast to existing SIP servers that are statically configured to either be stateless or stateful and therefore result in sub-optimal call throughput. We implement SERvartuka on top of OpenSER, a commercial SIP proxy server and measure performance benefits of different server configurations. An example of our results is a 20% percent increase in call throughput when using our algorithm for a configuration of two servers in series.

In this paper, we analyse the data sharing mechanisms of *nix systems and identify an immediate need for better privacy support. For example, using a simple insider attack we were able to access over 84 GB of private data at one organisation of 825 users, including 300 000 e-mails and 579 passwords to financial and other private services websites, without exploiting any technical vulnerability. We present two solutions to address this problem: 1. an administrative auditing tool which can alert administrators and users when their private data is at risk; 2. a new View Based Access Control (VBAC) mechanism which provides stronger and yet convenient privacy support. We also describe a proof-of-concept filesystem-based implementation and performance analysis of VBAC. Our evaluations with three well-known filesystem benchmarks show little overhead of using VBAC.

Reputation systems provide a promising way for building trust through social control in collaborative communities by harnessing the community knowledge in the form of feedback. However, reputation systems also introduce vulnerabilities due to potential manipulations by dishonest or malicious players. In this paper, we focus on two closely related problems - feedback sparsity and potential feedback manipulations - and propose a feedback similarity based inference framework. We perform extensive evaluations of various algorithmic components of the framework and evaluate their effectiveness on countering feedback sparsity in the presence of feedback manipulations.

As most blogs and traditional media support RSS or Atom feeds, the news feed technology becomes increasingly prevalent. Taking advantage of ubiquitous news feeds, we design FeedEx, a news feed exchange system. Forming a distribution overlay network, nodes in FeedEx not only fetch feed documents from the servers but also exchange them with neighbors. Among many benefits of collaborative feed exchange, we focus on the low-overhead, scalable delivery mechanism that increases the availability of news feeds. Our design of FeedEx is incentive-compatible so that nodes are encouraged into cooperating rather than free riding. In addition, for a better design of FeedEx, we analyze the data collected from 245 feeds for 10 days and present relevant statistics about news feed publishing, including the distributions of feed size, entry lifetime, and publishing rate.Our experimental evaluation using 189 PlanetLab machines, which fetch from real-world feed servers, shows that FeedEx is an efficient system in many respects. Even when a node fetches feed documents as infrequently as every 16 hours, it captures more than 90% of the total entries published, and those captured entries are available within 22 minutes on average after published at the servers. By contrast, stand-alone applications in the same condition show 36% of entry coverage and 5.7 hours of time lag. The efficient delivery of FeedEx is achieved with low communication overhead as each node receives only 0.9 document exchange calls and 6.3 document checking calls per minute on average.

Current trends in distributed computing have been moving towards the use of wide-area clusters that are managed by different entities. In this paper, we introduce middleware-level support to facilitate computational resource sharing with service guarantees using non-dedicated server systems in wide-area clusters. The aim is to ensure that sets of computational tasks submitted to such high end systems are completed reliably and in a timely fashion. Our approach develops methods that enhance basic job scheduling with information about the execution history and trust values for the computational nodes to which jobs are assigned. In essence, job scheduling is enriched with trust models constructed and maintained at runtime, and scheduling decisions are based on metrics that capture trust in remote server systems. An implementation of the approach is evaluated on Planetlab, with initial results demonstrating good success rates in completing jobs within their specific service level agreements, including under conditions of high system loads. Additional results are attained with a variant of the scheduling algorithm that uses redundancy to further improve the likelihood of meeting end user SLAs. A representative application considered in this paper is remote data visualization, where substantial computation must be applied to data before displaying it to end users. SLAs capture desired end-to-end delay, and distributed server or cluster systems are used to perform the required computations in a timely manner

We consider heterogeneous group communication in which users have different preference for information related to various topics. The problem of disseminating such information to interested set of users in an overlay network is challenging when both low end-to-end latency and low incurred overlay traffic are desired. We investigate heuristic based overlay topology generation algorithm that exploits both network proximity in underlying network and similarity between users' preferences to reduce both the overlay latency and the amount of data forwarding done by nodes that do not prefer the data. Our results show that while these requirements conflict, an application specific tradeoff can be made to improve the overall system performance.

The open nature of peer-to-peer systems has played an important role in their growing popularity. The current file-sharing applications, for instance, have been widely used largely because they allow anyone to participate in them. This openness, however, brings up new issues because selfish, malicious, faulty, compromised, or resource-constrained peers may degrade a system. We explore the case for large-scale information dissemination through the design of the Trust-Aware Multicast (TAM) protocol. Nodes in TAM can exhibit uncooperative behavior such as delaying, discarding, modifying, replaying, and fabricating messages. While detecting such behaviors, TAM computes a level of trust for each node and adapts the underlying multicast tree according to trustworthiness of nodes, which leads to performance improvement in the system. The results from our simulation and PlanetLab experiments show that even with a significant portion of nodes being uncooperative, TAM is able to build a stable dissemination tree that provides lower message delay to well-behaved nodes.

Heterogeneous users usually have different requirements as far as consistency of shared data is concerned. This paper proposes and investigates a mixed consistency model to meet this heterogeneity challenge in large scale distributed systems that support shared objects. This model allows combining strong (Sequential) consistency and weak (Causal) consistency. The paper defines the model, motivates it and proposes a protocol implementing it.

The scalability of a distributed service can be improved if the number of replicated instances of the service can vary with the load experienced by the system. To ensure that the number and placement of the replicas can be dynamically changed based on network and load conditions, a peer node must know when it should create a new replica and when such a replica can be removed. A scheme that makes such decisions centrally suffers from a number of problems. In this paper, we propose a self-managing replication algorithm for a peer-to-peer system where a peer node makes its decisions based on its locally maintained information. This algorithm offers several benefits. They include being responsive to heterogeneous load and ensuring that each peer node fairly contributes its available resources to meet the needs of the overall system. It is evaluated with simulations of a system that consists of one thousand nodes. Our results show that this self-managing algorithm can maintain a replication degree that adapts to load in the system and achieve a low response time.

Information visualization is an effective way to easily comprehend large amounts of data. For such systems to be truly effective, the information visualization designer must be aware of the ways in which their system may be manipulated and protect their users from attack. In addition, users should be aware of potential attacks in order to minimize or negate their effect. These attacks target the information visualization system as well as the perceptual, cognitive and motor capabilities of human end users. To identify and help counter these attacks we present a framework for information visualization system security analysis, a taxonomy of visualization attacks and technology independent principles for countering malicious visualizations. These themes are illustrated with case studies and working examples from the network security visualization domain, but are widely applicable to virtually any information visualization system.

Quorum protocols offer several benefits when used to maintain replicated data but techniques for reducing overheads associated with them have not been explored in detail. It is desirable that a system be able to adapt its operation so that fault tolerance related overheads are only incurred when the protocol execution actually encounters faults. There are a number of issues that need to be carefully examined to achieve such agility of quorum based systems. We make use of a file system prototype, developed in our Agile Store project, to experimentally evaluate several techniques that are important for efficient implementation of Byzantine fault-tolerant quorum protocols. We present an optimistic quorum collection scheme and a probabilistic hashing scheme for determining the response to a quorum request, and show that they lead to significant performance improvements. The Agile Store also makes use of reconfigurable quorum techniques to allow system size and fault threshold to be dynamically varied when, for example, faulty servers are removed, new servers are added, or the threat level is changed. We quantify the performance gains made possible by such reconfiguration of quorum parameters. We also show how performance scales with different system parameters and how it is affected by design choices such as whether to use proxies. We believe that the results in the paper provide important insights into how to implement quorum protocols to provide good performance while achieving Byzantine fault tolerance.

This paper explores the application of visualization techniques to aid in the analysis of malicious and non-malicious binary objects. These objects may include any logically distinct chunks of binary data such as image files, word processing documents and network packets. To facilitate this analysis, we present a novel visualization technique for comparing and navigating among 600-1000+ such objects at one time. While the visualization technique alone has powerful application for both directed and undirected exploration of many classes of binary objects, we chose to study network packets. To increase effectiveness, we strengthened the visualization technique with novel, domain-specific semantic zooming, interactive encoding and dynamic querying capabilities. We present results and lessons learned from implementing these techniques and from studying both malicious and non-malicious network packets. Our results indicate that the information visualization system we present is an efficient and effective way to compare large numbers of network packets, visually examine their payloads and navigate to areas of interest within large network datasets.

We consider the problem of disseminating an update known to a set of servers to other servers in the system via a gossip protocol. Some of the servers can exhibit malicious behavior. We require that only the updates introduced by authorized clients are accepted by non-malicious servers. Spurious updates, in particular those generated by compromised nodes, are not accepted by non-malicious servers. We take the approach of collective endorsement where each server endorses an accepted update by computing a list of message authentication codes with symmetric keys allocated to it. We use a novel key allocation scheme that allocates a set of symmetric keys to each participating server to minimize the total number of keys. Our protocol is designed to minimize update diffusion time. In the absence of faulty nodes, its diffusion time is O(log n), which is the best possible time achieved when nodes only suffer from benign faults. If the actual number of Byzantine faults experienced during an update's dissemination is f, diffusion time increases to O(log n) + f. This is better than the latency of previously known protocols that take O(log n) +b time, where b is the assumed threshold that defines the maximum number of malicious servers that can be tolerated rather than f, the actual number of failures. The buffer requirements and message sizes are higher in our protocol than other known protocols, thus it trades off memory and bandwidth resources to improve latency.

We present the design of a distributed store that offers various levels of security guarantees while tolerating a limited number of nodes that are compromised by an adversary. The store uses secret sharing schemes to offer security guarantees namely availability, confidentiality and integrity. However, a pure secret sharing scheme could suffer from performance problems and high access costs. We integrate secret sharing with replication for better performance and to keep access costs low. The tradeoffs involved between availability and access cost on one hand and confidentiality and integrity on the other are analyzed. Our system differs from traditional approaches such as state machine or quorum based replication that have been developed to tolerate Byzantine failures. Unlike such systems, we augment replication with secret sharing and demonstrate that such a hybrid scheme offers additional flexibility that is not possible with replication alone.

Quorum-based protocols can be used to manage data when it is replicated at multiple server nodes to improve availability and performance. If some server nodes can be compromised by a malicious adversary, Byzantine quorums must be used to ensure correct access to replicated data. This paper introduces reconfigurable Byzantine quorums, which allow various quorum protocol parameters to be adapted based on the behavior of compromised nodes and the performance needs of the system. We present a protocol that generalizes dynamic Byzantine quorums by allowing the system size to change as faulty servers are removed from the system, in addition to adapting the fault threshold. A new architecture and algorithm that provide the capability to detect and remove faulty servers are also described. Finally, simulation results are presented that demonstrate the benefits offered by our approach.

We present the design of a distributed store that offers various levels of security guarantees while tolerating a limited number of nodes that are compromised by an adversary. The store uses secret sharing schemes to offer security guarantees, namely, availability, confidentiality, and integrity. However, a pure secret sharing scheme could suffer from performance problems and high access costs. We integrate secret sharing with replication for better performance and to keep access costs low. The trade offs involved between availability and access cost on one hand and confidentiality and integrity on the other are analyzed. Our system differs from traditional approaches such as state machine or quorum-based replication that have been developed to tolerate Byzantine failures. Unlike such systems, we augment replication with secret sharing and offer weaker consistency guarantees. We demonstrate that such a hybrid scheme offers additional flexibility that is not possible with replication alone.

We describe an approach to building security services for context-aware environments. Specifically, we focus on the design of security services that incorporate the use of security-relevant "context" to provide flexible access control and policy enforcement. We previously presented a generalized access control model that makes significant use of contextual information in policy definition. This document provides a concrete realization of such a model by presenting a system-level service architecture, as well as early implementation experience with the framework. Through our context-aware security services, our system architecture offers enhanced authentication services, more flexible access control and a security subsystem that can adapt itself based on current conditions in the environment. We discuss our architecture and implementation and show how it can be used to secure several sample applications.

As applications enabled by the Internet become information rich, ensuring access to quality information in the presence of potentially malicious entities will be a major challenge. Denial of information (DoI) attacks attempt to degrade the quality of information by deliberately introducing noise that appears to be useful information. The mere availability of information is insufficient if the user must find a needle in a haystack of noise that is created by an adversary to hide critical information. We focus on the characterization of information quality metrics that are relevant in the presence of DoI attacks. In particular, two complementary metrics are explored. Information regularity captures predictability in the patterns of information creation and access. The second metric, information quality trust, captures the known ability of an information source to meet the needs of its clients.

Distributed applications that access persistent objects must maintain object state consistency even when failures are encountered during the manipulation of such objects. The basic transaction model, which has been implemented by several systems to ensure consistent executions of distributed applications, is not flexible enough to meet the requirements of many complex distributed applications. This has also been recognized for advanced database applications and, as a result, extended transaction models have been developed. We argue that distributed applications that manipulate long-lived data can benefit from such transaction models. We take an approach which views the various transaction models as policies for building robust applications. Thus, we advocate that the system implement several transaction models. A robust application can be programmed in such a system using a combination of several transaction models to meet its consistency requirements. We use applications from the domain of computer-supported cooperative work to motivate such an approach. We also develop a set of system-level mechanisms which can be used to implement multiple transaction models in a uniform manner. These mechanisms are used to implement nested, split, and cooperating transaction models. A prototype system that has been implemented is described to demonstrate the feasibility of this approach.

As computers become pervasive in environments like the home and community, data repositories that can maintain the long term state of applications will become increasingly important. Because of the greater reliance of people on such applications and the potentially sensitive nature of the data manipulated by them, the repository must be highly available and it should provide secure access to data. Furthermore, many different types of data, ranging from private data belonging to a single user to data shared across different users may be stored in the repository. We present the design of a distributed data repository, called a secure store, which can meet the data access needs of diverse applications. We develop protocols that replicate data at multiple servers to enhance availability, and work even when a limited number of compromised servers exhibit arbitrary failure behavior. We also discuss how the nature of the data that is stored in the secure store impacts the availability and costs associated with data access.

Distributed applications that share a dynamically changing state are increasingly being deployed in wide-area environments. Such applications must access the state in a consistent manner, but the consistency requirements vary significantly from other systems. For example, shared memory models, such as sequential consistency, focus on the ordering of operations, and the same level of consistency is provided to each process. In interactive distributed applications, the timeliness of updates becoming effective could be an extremely important consistency requirement, and it could be different across different users. We propose a system that provides both non-timed and time-sensitive read and write operations for dynamic shared state. For example, a timed read can be used by a process to read a recently written value, whereas a timed write can make a new value available to all readers within a certain amount of time. We develop a consistency model that precisely defines the semantics of timed and non-tinted read and write operations. A protocol that implements this model is also presented. We also describe an implementation and some performance measurements.

Generalized Role-Based Access Control (GRBAC) is a new paradigm for creating and maintaining rich access control policies. GRBAC leverages and extends the power of traditional role based access control (RBAC) by incorporating subject roles, object roles and environment roles into access control decisions. Subject roles are like traditional RBAC roles: they abstract the security-relevant characteristics of subjects into categories that can be used in defining a security policy. Similarly, object roles abstract the various properties of objects, such as object type (e.g., text, JPEG, executable) or sensitivity level (e.g., classified, top secret) into categories. Environment roles capture environmental information, such as time of day or system load so it can be used to mediate access control. Together, these three types of roles offer flexibility and expressive power, as well as a degree of usability not found in current access control models.

In the future, a largely invisible and ubiquitous computing infrastructure \nwill assist people with a variety of activities in the home and at work. \nThe applications that will be deployed in such systems will create and \nmanipulate private information and will provide access to a variety of other \nresources. Securing such applications is challenging for a number of \nreasons. Unlike traditional systems where access control has been explored, \naccess decisions may depend on the context in which requests are made. We \nshow how the well-developed notion of roles can be used to capture \nsecurity-relevant context of the environment in which access requests are \nmade. By introducing environment roles, we create a uniform access control \nframework that can be used to secure context-aware applications. We also \npresent a security architecture that supports security policies that make \nuse of environment roles to control access to resources.

Interactive distributed applications are a relatively new class of applications that are enabled by sharing continuously evolving data across distributed sites (and users). The characteristics of application data include very fine-grained updates that can atomically access a subset of the shared data, masking of update effects, and irregular locality and contention for access. Existing programming approaches are not appropriate for programming such continuous shared data in a wide-area environment.

A common class of wide-area distributed applications remotely collect time-varying data and send it to consumers around the network. Some examples of these include network management, stock ticker data and event logs. The environment in which these applications must operate often dictates the schemes for disseminating the data between the writers and the readers. If the transport channel can be optimized to match the application's behavior patterns and the network resource constraints, sufficient improvements in application-level quality of service (QoS) can be achieved. The PASS (Piecewise Asynchronous Sample Service) system addresses this problem by using a flexible system of interconnected servers. PASS servers are distributed geographically around the network and are connected to readers and writers using the CORBA protocol. The forwarding policies used by the servers and the server interconnections can be customized for each application. Thus, PASS acts like an application-level multicast service with variable forwarding policies. PASS has been used to disseminate the up/down status of a large number of devices to a network management system. The PASS forwarding policy used very little network bandwidth while responding to failures in half a network round-trip time.

Ordering and time are two different aspects of consistency of shared objects in a distributed system. One avoids conflicts between operations, the other addresses how quickly the effects of an operation are perceived by the rest of the system. Consistency models such as sequential consistency and causal consistency do not consider the particular time at which an operation is executed to establish a valid order among all the operations of a computation. Timed consistency models require that if a write operation is executed at time t, it must be visible to all nodes by time t+D. Timed consistency generalizes several existing consistency criteria and it is well suited for interactive and collaborative applications, where the action of one user must be seen by others in a timely fashion.

No abstract available.

A common way to address scalability requirements of distributed services is to employ server replication and client caching of objects that encapsulate the service state. The performance of such a system could depend very much on the protocol implemented by the system to maintain consistency among object copies. We explore scalable consistency protocols that never require synchronization and communication between all nodes that have copies of related objects. We achieve this by developing a novel approach called local consistency (LC). LC based protocols can provide increased flexibility and efficiency by allowing nodes control over how and when they become aware of updates to cached objects. We develop two protocols for implementing strong consistency using this approach and demonstrate that they scale better than a traditional invalidation based consistency protocol along the system load and geographic distribution dimensions of scale.

Distributed services that are accessed by widely distributed clients are becoming common place. Such services cannot be provided at the needed level of performance and availability without replicating the service at multiple nodes, and without allowing a relatively weak level of consistency among replicated copies of the state of a service. This paper explores causally consistent distributed services when multiple related services are replicated to meet performance and availability requirements. This consistency criterion is particularly well suited for some distributed services (e.g., cooperative document sharing), and it is attractive because of the efficient implementations allowed by it.

The paper presents our state sharing support for building object oriented interactive groupware in wide area distributed environments. We motivate and present an asynchronous model for updating replicated state, which supports atomicity of updates across multiple shared objects. Coupled with our flexible marshalling framework, this model allows existing application data structure classes to be easily extended and made shareable. To solve the problem of replica consistency we use a novel combination of three mechanisms: (1) global locks, (2) detection of incorrect update ordering, and (3) cloning a subset of the shared objects and state reinitialization. Finally, to reduce network load due to fine grain user interaction, we provide a framework for application specified event batching called Late Event Modification.

We present the Mocha wide area computing infrastructure we are developing. Mocha provides support for robust shared objects on heterogeneous platforms, and utilizes advanced distributed shared memory techniques for maintaining consistency of shared objects that are replicated at multiple nodes to improve performance. In addition, our system handles failures that we feel will be common in wide area environments. We have used an approach that makes use of multiple communication protocols to improve the efficiency of shared object state transfers in Mocha. We also provide an empirical evaluation of our prototype implementation for local area, wide area, and home service networks and present a sample home service application that has been programmed with the system.

No abstract available.

Distributed systems that consist of workstations connected by high performance interconnects offer computational power comparable to moderate size parallel machines. Middleware like distributed shared memory (DSM) or distributed shared objects (DSO) attempts to improve the programmability of such hardware by presenting to application programmers interfaces similar to those offered by shared memory machines. This paper presents the portable Indigo data sharing library which provides a small set of primitives with which arbitrary shared abstractions are easily and efficiently implemented across distributed hardware platforms. Sample shared abstractions implemented with Indigo include DSM as well as fragmented objects, where the object state is split across different machines and where interfragment communications may be customized to application-specific consistency needs. The Indigo library's design and implementation are evaluated on two different target platforms: a workstation cluster and an IBM SP2 machine. As part of this evaluation, a novel DSM system and consistency protocol are implemented and evaluated with several high performance applications. Application performance attained with the DSM system is compared to the performance experienced when utilizing the underlying basic message-passing facilities or when employing Indigo to construct customized fragmented objects implementing the application's shared state. Such experimentation results in insights concerning the efficient implementation of DSM systems (e.g. how to deal with false sharing). It also leads to the conclusion that Indigo provides a sufficiently rich set of abstractions for efficient implementation of the next generation of parallel programming models for high performance machines. © 1998 John Wiley & Sons, Ltd.

Gigabit network technologies have made it possible to combine workstations into a distributed, massively-parallel computer system. Middleware, such as distributed shared objects (DSO), attempts to improve programmability of such systems, by providing globally accessible 'object' abstractions. Researchers have developed consistency protocols for replicated 'memory' objects. These protocols are well suited to scientific applications but less suited to multimedia or groupware applications. We address the state sharing needs of complex distributed applications with: high-frequency symmetric accesses to shared objects; unpredictable and limited locality of accesses; dynamically changing sharing behavior; and potential data races. We show that a DSO system exploiting application-level temporal and spatial constraints on shared objects can outperform shared object protocols which do not exploit application-level constraints. We compare our S(emantic) DSO against entry consistency using a sample application having the four properties mentioned above.

In large scale distributed systems, caching and replication could greatly speedup access and increase availability. Consistency of replicated state can be guaranteed by forcing operations to occur in the same order at all sites. However some applications can preserve correctness with weaker consistency requirements leading to better performance. We propose an object lifetime based mutual consistency detection mechanism that is used to implement multiple consistency levels. This mechanism provides scalable implementations because caching overheads at client nodes depend only on the accesses done at the node. A contribution of this paper is the separation of the the mutual consistency detection mechanism from the policy that decides the desired consistency guarantees. This allows multiple consistency levels to coexist, thus improving system performance through the use of weaker consistency levels when possible. Besides improving performance, the mechanism allows for a graceful weakening of consistency requirements when stronger requirements cannot be maintained, as in the case of disconnection that can be experienced in mobile environments. The mutual consistency detection mechanism also provides a uniform way of hoarding a mutually consistent set of objects during voluntary disconnection.

No abstract available.

Distributed systems that consist of workstations connected by high performance interconnects offer computational power comparable to moderate size parallel machines. It is desirable that such workstation clusters can also be programmed the same way as shared memory machines. We develop a portable, user-level library, called Indigo, that can be used to program a variety of state sharing techniques. In particular, Indigo can be used to program DSM protocols as well as distributed shared abstractions where objects can be fragmented/replicated and consistency actions are customized according to application needs. We present an evaluation of Indigo by using its calls to implement a distributed shared memory system as well as shared abstractions for a number of applications.

Traditional transaction models ensure robustness for distributed applications through the properties of view and failure atomicity. It has generally been felt that such atomicity properties are restrictive for a wide range of application domains; this is particularly true for robust, collaborative applications because such applications have concurrent components that are inherently long-lived and that cooperate. Recent advances in extended transaction models can be exploited to structure long-lived and cooperative computations. Applications can use a combination of such models to achieve the desired degree of robustness; hence, we develop a system which can support a number of flexible transaction models, with correctness criteria that extend or relax serializability. We analyze two concrete CSCW applications-collaborative editor and meeting scheduler. We show how a combination of two extended transaction models, that promote split and cooperating actions, facilitates robust implementations of these collaborative applications. Thus, we conclude that a system that implements multiple transaction models provides flexible support for building robust collaborative applications.

Distributed shared memory consistency protocols suffer from poor performance due their lack of application spe cific knowledge which can be exploited in message passing systems. Explicit synchronization can be used in mem ory coherence activities to realize the benefits of applica tion specific information if the user is allowed to associate data with synchronization operations. In this paper, we present a refinement of synchronization and data sharing patterns and identify attributes that can be used to asso ciate data with suitably modified synchronization primi tives. We present modifications for semaphores, read-write locks, and barriers which can be used to implement a va riety of interaction patterns including mutual exclusion, producers-consumers, readers-writers etc. We claim that the performance of applications programmed using shared memory can be comparable to their message passing imple mentation which use intermediary entities such as mail boxes. On the other hand, programming is easier with our system, since it allows for richer patterns of interaction than when directly using low-level messages.

The traditional consistency requirements of shared memory are expensive to provide both in large scale multiprocessor systems and in distributed systems that implement a shared memory abstraction. As a result, several memory systems have been proposed that enhance performance and scalabil ity by providing weaker consistency. The differing models used to describe such memories make it difficult to relate and compare them. We develop a simple non-operational model and identify parameters that can be varied to de scribe existing memories and to identify new ones. We show how a uniform framework makes it easy to compare and relate various memories.

Shared memories that provide weaker consistency guarantees than the traditional sequentially consistent or atomic memories have been claimed to provide the key to building scalable systems.One influential memory model, processor considency, has been cited widely in the literature but, due to the lack of a precise and formal definition, contradictory claims have been made regarding its power.We use a formal model to give two distinct definitions of processors consistency: one corresponding to Goodman's original proposal and the other corresponding that given by the implementors of the DASH system.These definitions are non-operational and can be easily related to other types of memories.To illustrate the power of processor consistency, we exhibit a non-cooperative solution to the mutual exclusion problem that is correct with processor consistency.As a contrast, we show that Lamport's Bakery algorithm is not correct with processor consistency. 1

A new protocol for maintaining replicated data that can provide both high data availability and low response time is presented. In the protocol, the nodes are organized in a logical grid. Existing protocols are designed primarily to achieve high availability by updating a large fraction of the copies, which provides some (although not significant) load sharing. In the new protocol, transaction processing is shared effectively among nodes storing copies of the data, and both the response time experienced by transactions and the system throughput are improved significantly. The authors analyze the availability of the new protocol and use simulation to study the effect of load sharing on the response time of transactions. They also compare the new protocol with a voting-based scheme.>

A simple owner protocol for implementing a causal distributed shared memory (DSM) is presented, and it is argued that this implementation is more efficient than comparable coherent DSM implementations. Moreover, it is shown that writing programs for causal memory is no more difficult than writing programs for atomic shared memory.>

article Free Access Share on Multidimensional voting Authors: Mustaque Ahamad Georgia Institute of Technology, Atlanta Georgia Institute of Technology, AtlantaView Profile , Mostafa H. Ammar Georgia Institute of Technology, Atlanta Georgia Institute of Technology, AtlantaView Profile , Shun Yan Cheung Emory Univ., Atlanta, GA Emory Univ., Atlanta, GAView Profile Authors Info & Claims ACM Transactions on Computer SystemsVolume 9Issue 4Nov. 1991 pp 399–431https://doi.org/10.1145/118544.118552Online:01 November 1991Publication History 37citation564DownloadsMetricsTotal Citations37Total Downloads564Last 12 Months17Last 6 weeks3 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A concept called multidimensional voting, in which the vote and quorum assignments are k-dimensional vectors of nonnegative integers and each dimension is independent of the others, is introduced. Multidimensional voting is more powerful than traditional weighted voting because it is equivalent to the general method for achieving synchronization in distributed systems which is based on coteries (sets of groups of nodes), but its implementation is easier than that of coteries. An efficient algorithm for finding a multidimensional vote assignment for any given coterie is described and examples of its use are shown. It is shown how multidimensional voting can be used to easily implement novel algorithms for synchronizing access to replicated data or to ensure mutual exclusion. These algorithms cannot be implemented by traditional weighted voting.>

The use of weakly consistent memories in distributed shared memory systems to combat unacceptable network delay and to allow such systems to scale is proposed. Proposed memory correctness conditions are surveyed, and how they are related by a weakness hierarchy is demonstrated. Multiversion and messaging interpretations of memory are introduced as means of systematically exploring the space of possible memories. Slow memory is presented as a memory that allows the effects of writes to propagate slowly through the system, eliminating the need for costly consistency maintenance protocols that limit concurrency. Slow memory processes a valuable locality property and supports a reduction from traditional atomic memory. Thus slow memory is as expressive as atomic memory. This expressiveness is demonstrated by two exclusion algorithms and a solution to M.J. Fischer and A. Michael's (1982) dictionary problem on slow memory.>

A protocol for maintaining replicated data that can provide both high data availability and low response time is presented. Existing protocols are designed primarily to achieve high availability by updating a large fraction of the copies, which provides some (although not significant) load sharing. In the new protocol, transaction processing is shared effectively among nodes storing copies of the data, and both the response time experienced by transactions and the system throughput are improved significantly. Also presented is an analysis of the availability of the new protocol and simulation is used to study the effect of load sharing on the response time of transactions. The new protocol is also compared with a voting-based scheme.>

The process of searching for a resource in a distributed system whose nodes are connected through a store-and-forward network is modeled. Based on this model, a lower bound on the number of messages needed for finding a resource when nothing is known about its location is shown. The model also helps to establish some results about the complexity of finding optimal algorithms to locate a resource when the probability distribution for the location of the resource is known. It is shown that the optimization problem is NP-hard for general networks. An algorithm is developed for tree networks which can be specialized to polynomial algorithms for a class of trees. (The polynomial algorithms can be used as the basis of heuristic algorithms for general networks.) An application of this algorithm for path networks can be adapted to find optimal search algorithms for bidirectional ring networks.>

Heuristics for constructing low-cost multicast spanning trees in a dynamic environment are investigated. Two heuristic algorithms are developed that update the multicast tree incrementally as the membership changes and reduce the total bandwidth required for sending data and control messages. The broadcast tree based algorithm makes use of a tree structure in the network, and the other algorithm joins a new member to the node that is nearest to it and is already in the multicast tree. A simulation model is used to study the performance of the algorithms and to compare them with the best-known heuristic algorithm developed by D.W. Wall (1980) which computes the multicast tree structure for a given membership of the group.>

The problem is discussed of determining the vote assignment and quorum that yields the highest availability in a system where node availabilities can be different and the mix of the read and write operations is arbitrary. For this purpose, an enumeration algorithm is presented that can be used to find the vote and quorum assignments that need to be considered for achieving optimal availability. An analytical method is derived to evaluate the availability of a given system for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The algorithm can also be used to obtain the optimal performance when other measures are considered.>

A protocol is presented to locate (or find) named resources in a distributed system which uses the multicast capabilities of the underlying network. Each node in the network uses a sequence of node groups, and each node group is associated with a unique multicast address. To locate a resource, the searching node sequentially polls each one of the groups until the resource is found; this scheme is a generalization of both pure polling and broadcast. To obtain an optimal division of the nodes into multicast groups, the protocol is analyzed and an efficient algorithm is given that provides a group division minimizing the expected cost per location operation.>

A multicast-based algorithm is proposed for load balancing in a local computer network. The ability of a host to make its membership known to a multicast group based on its workload makes it possible to send a transfer request only to those hosts which have lower workload than the host that wants to transfer a task. This reduces the overhead of load balancing because a host does not waste computational resources when it cannot accept a task. The authors use a simulation model to investigate the performance of the multicast based algorithm and compare it favorably to algorithms that use unicast (point-to-point) communication.>

A checkpointing scheme can be used to ensure forward progress of a computation (program) even when failures occur. In a distributed system, many autonomous programs can execute concurrently and obtain services from a set of shared servers. In such a system, it is desirable to to restrict a checkpoint or rollback operation to a single program to localize the effects of failures, even when processes of different programs communicate with servers. This can be achieved by a scheme based on message logging and consistent checkpoints when the system is deterministic. When the system (communication network or programs) is nondeterministic, the semantics of the server functions should be exploited to reduce the additional synchronization that needs to be introduced to ensure locality. The authors illustrate this by presenting efficient algorithms for a file server that do not require the logging of messages on stable storage.>

In the weighted voting protocol which is used to maintain the consistency of replicated data, the availability of the data to ready and write operations not only depends on the availability of the nodes storing the data but also on the vote and quorum assignments used. The authors consider the problem of determining the vote and quorum assignments that yield the best performance in a distributed system where node availabilities can be different and the mix of the read and write operations is arbitrary. The optimal vote and quorum assignments depend not only on the system parameters, such as node availability and operation mix, but also on the performance measure. The authors present an enumeration algorithm that can be used to find the vote and quorum assignments that need to be considered for achieving optimal performance. When the performance measure is data availability, an analytical method is derived to evaluate it for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The enumeration algorithm can also be used to obtain the optimal performance when other measures are considered.>

The authors develop a model and define performance measures for a replicated data system that makes use of a quorum-consensus algorithm to maintain consistency. They consider two measures: the proportion of successfully completed transactions in systems where a transaction aborts if data is not available, and the mean response time in systems where a transaction waits until data becomes available. Based on the model, the authors show that for some quorum assignment there is an optimal degree of replication beyond which performance degrades. There exist other quorum assignments which have no optimal degree of replication. The authors also derive optimal read and write quorums which maximize the proportion of successful transactions.>

The authors address the problem of determining how system parameters affect the performance of the location operations when hint tables are used. To this end they approximate a distributed system incorporating hint tables in its location strategy with an analytic model. They identify a set of parameters affecting the cost of location operations and provide a criterion to help decide whether the use of hint tables should be incorporated in the design of a given system. They give a set of examples to illustrate the usage of the analytic results. These include location using: broadcast in a broadcast network; name servers in a broadcast network; broadcast is a packet switched network and name servers in a packet switched network.>

The authors present a resource (e.g. file, process) location scheme which utilizes the multicast communication capability of local area networks (LANs). In the scheme, the universe of resource names is partitioned into a relatively small number of groups and each group is assigned a unique address. Nodes storing the locations of resources belonging to a particular group instruct their network interfaces to receive all location messages sent to the group address. To locate a resource, a node first determines the address of the group to which the resource belongs, and a multicast message is then sent to the address. The algorithm performance is studied by simulation, and approximate closed-form solutions are derived for systems operating at heavy and low loads. The scheme's performance is compared with that of broadcast, and it is shown that the proposed scheme performs much better than broadcast alone.>

An interprocess communication structure for a distributed language is described which provides message level communication, multicast, and a generalized naming facility. The design is oriented to the needs of low level algorithms which, for example, might be used in a distributed operating system to support resource allocation or enhance reliability. The proposal is illustrated by programming several distributed algorithms from the literature. An implementation is described that takes advantage of physical multicast technology, and reduces to more conventional schemes for common communication paradigms.