|
Interference Freedom
In computer science, interference freedom is a technique for proving partial correctness of concurrent programs with shared variables. Hoare logic had been introduced earlier to prove correctness of sequential programs. In her PhD thesis (and papers arising from it ) under advisor David Gries, Susan Owicki extended this work to apply to concurrent programs. Concurrent programming had been in use since the mid 1960s for coding operating systems as sets of concurrent processes (see, in particular, Dijkstra. ), but there was no formal mechanism for proving correctness. Reasoning about interleaved execution sequences of the individual processes was difficult, was error prone, and didn't scale up. Interference freedom applies to ''proofs'' instead of execution sequences; one shows that execution of one process cannot interfere with the correctness proof of another process. A range of intricate concurrent programs have been proved correct using interference freedom, and interference ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical disciplines (including the design and implementation of Computer architecture, hardware and Computer programming, software). Computer science is generally considered an area of research, academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing Vulnerability (computing), security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Progr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Summer School Marktoberdorf
The International Summer School Marktoberdorf is an annual two-week summer school for international computer science and mathematics postgraduate students and other young researchers, held annually since 1970 in Marktoberdorf, near Munich in southern Germany. Students are accommodated in the boarding house of a local high school, Gymnasium Marktoberdorf. Proceedings are published when appropriate. Status This is a summer school for theoretical computer science researchers, with some directors/co-directors who are Turing Award winners (the nearest equivalent to the Nobel Prize in computer science). The summer school is supported as an Advanced Study Institute of the NATO Science for Peace and Security Program. It is administered by the Faculty of Informatics at the Technical University of Munich. Directors Past academic directors and co-directors include: * Manfred Broy *Robert Lee Constable *Javier Esparza * Orna Grumberg *David Harel *Tony Hoare* *Orna Kupferman *Tobias Nip ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dekker's Algorithm
Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming where processes only communicate via shared memory. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process descriptions and his manuscript on cooperating sequential processes. It allows two threads to share a single-use resource without conflict, using only shared memory for communication. It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented. Overview If two processes attempt to enter a critical section at the same time, the algorithm will allow only one process in, based on whose it is. If one process is already in the critical section, the other process will busy wait for the first process to exit. This is done by the use of two flags, and , which indicate an intention to enter the critical section on the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
UNITY (programming Language)
UNITY is a programming language constructed by K. Mani Chandy and Jayadev Misra for their book ''Parallel Program Design: A Foundation''. It is a theoretical language which focuses on ''what'', instead of ''where'', ''when'' or ''how''. The language contains no method of flow control, and program statements run in a nondeterministic way until statements cease to cause changes during execution. This allows for programs to run indefinitely, such as auto-pilot or power plant safety systems, as well as programs that would normally terminate (which here converge to a fixed point). Description All statements are assignments, and are separated by #. A statement can consist of multiple assignments, of the form a,b,c := x,y,z, or a := x , , b := y , , c := z. You can also have a ''quantified statement list'', <# x,y : ''expression'' :: ''statement''>, where x and y are chosen randomly among the values that satisfy ''expression''. A ''quantified assignment'' is similar. In < ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jayadev Misra
Jayadev Misra is an Indian-born computer scientist who has spent most of his professional career in the United States. He is the Schlumberger Centennial Chair Emeritus in computer science and a University Distinguished Teaching Professor Emeritus at the University of Texas at Austin. Professionally he is known for his contributions to the formal aspects of concurrent programming and for jointly spearheading, with Sir Tony Hoare, the project on Verified Software Initiative (VSI). Education and early career Misra received a B.Tech. in electrical engineering from IIT Kanpur, India in 1969 and a Ph.D. in electrical engineering and computer science from the Johns Hopkins University, Baltimore, Maryland in 1972. After a brief period working for IBM, he joined the University of Texas at Austin in 1974 where he has remained throughout his career, except for a sabbatical year spent at Stanford University during 1983–1984. He retired from active teaching in 2015. Major professional c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Safety And Liveness Properties
Properties of an execution of a computer program —particularly for concurrent and distributed systems— have long been formulated by giving ''safety properties'' ("bad things don't happen") and ''liveness properties'' ("good things do happen"). A simple example will illustrate safety and liveness. A program is totally correct with respect to a precondition P and postcondition Q if any execution started in a state satisfying P terminates in a state satisfying Q. Total correctness is a conjunction of a safety property and a liveness property: * The safety property prohibits these "bad things": executions that start in a state satisfying P and terminate in a final state that does not satisfy Q. For a program C, this safety property is usually written using the Hoare triple \ C \. * The liveness property, the "good thing", is that execution that starts in a state satisfying P terminates. Note that a ''bad thing'' is discrete, since it happens at a particular place during execution. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Peter O'Hearn
Peter William O'Hearn One or more of the preceding sentences incorporates text from the royalsociety.org website where: (born 13 July 1963 in Halifax, Nova Scotia), formerly a research scientist at Meta, is a Distinguished Engineer at Lacework and a Professor of Computer science at University College London (UCL). He has made significant contributions to formal methods for program correctness. In recent years these advances have been employed in developing industrial software tools that conduct automated analysis of large industrial codebases. Education O'Hearn attained a BSc degree in computer science from Dalhousie University, Halifax, Nova Scotia (1985), followed by MSc (1987) and PhD (1991) degrees from Queen's University, Kingston, Ontario, Canada. His dissertation was on ''Semantics of Non-interference: A natural approach'', supervised by Robert D. Tennent. [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Concurrent Separation Logic
In computer science, separation logic is an extension of Hoare logic, a way of reasoning about programs. It was developed by John C. Reynolds, Peter O'Hearn, Samin Ishtiaq and Hongseok Yang, drawing upon early work by Rod Burstall. The assertion language of separation logic is a special case of the logic of bunched implications (BI). A CACM review article by O'Hearn charts developments in the subject to early 2019. Overview Separation logic facilitates reasoning about: * programs that manipulate pointer data structures—including information hiding in the presence of pointers; * ''"transfer of ownership"'' (avoidance of semantic frame axioms); and * virtual separation (modular reasoning) between concurrent modules. Separation logic supports the developing field of research described by Peter O'Hearn and others as ''local reasoning'', whereby specifications and proofs of a program component mention only the portion of memory used by the component, and not the entire global state ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Separation Logic
In computer science, separation logic is an extension of Hoare logic, a way of reasoning about programs. It was developed by John C. Reynolds, Peter O'Hearn, Samin Ishtiaq and Hongseok Yang, drawing upon early work by Rod Burstall. The assertion language of separation logic is a special case of the logic of bunched implications (BI). A CACM review article by O'Hearn charts developments in the subject to early 2019. Overview Separation logic facilitates reasoning about: * programs that manipulate pointer data structures—including information hiding in the presence of pointers; * ''"transfer of ownership"'' (avoidance of semantic frame axioms); and * virtual separation (modular reasoning) between concurrent modules. Separation logic supports the developing field of research described by Peter O'Hearn and others as ''local reasoning'', whereby specifications and proofs of a program component mention only the portion of memory used by the component, and not the entire global sta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cliff Jones (computer Scientist)
Clifford "Cliff" B. Jones (born 1 June 1944) is a British computer scientist, specializing in research into formal methods. He undertook a late DPhil at the Oxford University Computing Laboratory (now the Oxford University Department of Computer Science) under Tony Hoare, awarded in 1981. Jones' thesis proposed an extension to Hoare logic for handling concurrent programs, rely/guarantee. Prior to his DPhil, Jones worked for IBM, between the Hursley and Vienna Laboratories. In Vienna, Jones worked with Peter Lucas, Dines Bjørner and others on the Vienna Development Method (VDM), originally as a method for specifying the formal semantics of programming languages, and subsequently for specifying and verifying programs. Cliff Jones was a professor at the Victoria University of Manchester in the 1980s and early 1990s, worked in industry at Harlequin for a period, and is now a Professor of Computing Science at Newcastle University. He has been editor-in-chief of the ''Formal Aspe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Springer Verlag
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 in Berlin, it expanded internationally in the 1960s, and through mergers in the 1990s and a sale to venture capitalists it fused with Wolters Kluwer and eventually became part of Springer Nature in 2015. Springer has major offices in Berlin, Heidelberg, Dordrecht, and New York City. History Julius Springer founded Springer-Verlag in Berlin in 1842 and his son Ferdinand Springer grew it from a small firm of 4 employees into Germany's then second largest academic publisher with 65 staff in 1872.Chronology ". Springer Science+Business Media. In 1964, Springer expanded its business internationally, o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
