We present a simple algorithm for maintaining a replicated distributed dictionary which achieves high availability of data, rapid processing of atomic actions, efficient utilization of storage, and tolerance to node or network failures including lost or duplicated messages. It does not require transaction logs, synchronized clocks, or other complicated mechanisms for its operation. It achieves consistency contraints which are considerably weaker than serial consistency but nonetheless are adequate for many dictionary applications such as electronic appointment calendars and mail systems. The degree of consistency achieved depends on the particular history of operation of the system in a way that is intuitive and easily understood. The algorithm implements a "best effort" approximation to full serial consistency, relative to whatever internode communication has successfully taken place, so the semantics are fully specified even under partial failure of the system. Both the correctness of the algorithm and the utility of such weak semantics depend heavily on special properties of the dictionary operations.
We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition on interactions, we define the concept of stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all stably computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P ∩ RL. Several open problems and promising future directions are discussed.
A solution to the critical section problem, first posed by Dijkstra [1], is a fundamental requirement for concurrent program control. The problem is to ensure that no two processes are in a specified area of their programs (the critical section) at the same time. Improvements to Dijkstra's solution were made by Knuth [2], deBruijn [3], and Eisenberg and McGuire [4]. The situation, for a distributed system was considered by Lamport [5]. Rivest and Pratt [6] presented a solution for a distributed system where processes may repeatedly fail. The algorithms to be presented will be further improvements, where the comparisons will be made according to three measures: message size—the number of values the variable for interprocess communication can take on; fairness—the sequence in which waiting processes enter their critical sections; and time—the amount of time a process spends attempting to enter its critical section.
This paper examines the types of neighborhoods that black and white homebuyers have secured loans in during the recent housing boom and subsequent bust. We expand upon and refine previous research on locational attainment using loan-level data from the 1992–2010 Home Mortgage Disclosure Act (HMDA) combined with tract- and metropolitan-level data from the 1990, 2000, and 2010 Census and the American Community Survey. Multilevel models show that black homebuyers are moving into considerably more racially segregated neighborhoods than their white counterparts and that their access to "whiter" neighborhoods did not expand during the housing boom, even after controlling for the racial composition of the metropolitan area and other key ecological factors. Conversely, new white homebuyers have been moving into neighborhoods with greater percent black residents, which may be a contributing factor in observed declines in segregation during the past few decades. Additionally, black homebuyers in metropolitan areas with greater suburban growth were on average accessing homes in more integrated neighborhoods. Finally, the models explained considerably more of the variation in the neighborhood racial composition of whites compared to blacks. These findings are suggestive of a dual housing market, one in which the experiences of blacks are still systematically different than those of whites, despite expanded access to homeownership.
Freight transportation is a critical element of the transportation system and the economy of Los Angeles County, California. Freight transportation links the large consumer market, major manufacturing industry sector, and international trade network of Los Angeles to the rest of the United States and the world. As the agency responsible for transportation planning and programming in Los Angeles County, the Los Angeles County Metropolitan Transportation Authority needs comprehensive tools for understanding the demands of the freight transportation sector and the effects of transportation investment on this sector. A project was undertaken to design a comprehensive, innovative, multimodal modeling framework to support freight transportation decision making in Los Angeles County. The proposed modeling approach combines elements of two state-of-the-art freight modeling techniques: logistics chain modeling and tour-based truck modeling. The reasons for selecting this approach are described; background on the modeling techniques is provided; and integration of the two methods into a comprehensive modeling framework is discussed.
Article Free Access Share on Easy impossibility proofs for distributed consensus problems Authors: Michael J. Fischer Yale University, New Haven, CT Yale University, New Haven, CTView Profile , Nancy A. Lynch Mass. Inst. of Tech., Cambridge, MA Mass. Inst. of Tech., Cambridge, MAView Profile , Michael Merritt AT&T Bell Labs., Murray Hill, NJ and Mass. Inst. of Tech., Cambridge, MA AT&T Bell Labs., Murray Hill, NJ and Mass. Inst. of Tech., Cambridge, MAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 59–70https://doi.org/10.1145/323596.323602Online:01 August 1985Publication History 47citation743DownloadsMetricsTotal Citations47Total Downloads743Last 12 Months26Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
