A Methodology for the Design and Verification of Globally Asynchronous/Locally Synchronous Architectures

by Steven P. Miller

Recent advanced in model-checking have made it practical to formally verify the correctness of many complex synchronous systems (i.e., systems driven by a single clock). However, many computer systems are implemented by asynchronously composing several synchronous components, where each component has its own clock and these clocks are not synchronized. Formal verification of such Globally Asynchronous/Locally Synchronous (GA/LS) architectures is a much more difficult task. In this report, we describe a methodology for developing and reasoning about such systems. This approach allows a developer to start from an ideal system specification and refine it along two axes. Along one axis, the system can be refined one component at a time towards an implementation. Along the other axis, the behavior of the system can be relaxed to produce a more cost effective but still acceptable solution. We illustrate this process by applying it to the synchronization logic of a Dual Fight Guidance System, evolving the system from an ideal case in which the components do not fail and communicate synchronously to one in which the components can fail and communicate asynchronously. For each step, we show how the system requirements have to change if the system is to be implemented and prove that each implementation meets the revised system requirements through modelchecking.

48 pages, Paperback

Published June 28, 2013

About the author

Steven P. Miller (Ph.D., Vanderbilt University) is a historian of U.S. political culture, American religion, and the American South. Miller’s most recent book is The Age of Evangelicalism: America's Born-Again Years (Oxford University Press, 2014). His first book, Billy Graham and the Rise of the Republican South (2009), drew praise in the pages of The New York Times Book Review, Reviews in American History, and many other publications. It was nominated for the 2010 Merle Curti Award. Miller is the author of numerous scholarly and popular articles about the history of American religion and politics. He has written for such venues as Christian Century, History News Network, and Religion in American History. A resident of St. Louis, Missouri, Miller teaches U.S. and World History at Webster University and Washington University (University College).