13
Publications
Publications listed by category and date of publication.
Please observe the copyright notices posted here governing the use of material from this page.
Click for papers indexed by
ACM,
IEEE,
DBLP,
Springer,
CiteSeer, and
Google Scholar
Sort:
By Date: Newest publications first | Oldest publications first
By Category: Book Chapters | Conference Proceedings | Workshop Papers
By Publisher: ACM | ACTA | Cambridge | ETD | IEEE Xplore | None | Springer
Conference Proceedings
- Citation:
Scott M. Pike and Paolo A.G. Sivilotti, "Dining Philosophers with Crash Locality 1" in Proceedings of
ICDCS 2004,
pp. 22-29. © IEEE 2004.
Best Paper Award (1st place out of 475 submitted papers).
- Abstract:
Ideally, distributed algorithms isolate the side-effects of faults within local neighborhoods of impact. Failure locality quantifies this concept as the maximum radius of impact caused by a given fault. We present new locality results for the dining philosophers problem subject to crash failures. The optimal crash locality for dining is 0 in synchronous networks, but degrades to 2 in asynchronous networks. Using the eventually-perfect failure detector /spl diams/P , we construct the first known dining algorithms with crash locality 1 under partial synchrony. These algorithms close the failure-locality complexity gap and improve the crash tolerance of resource allocation algorithms in practical networks. We prove the optimality of our results with two fundamental theorems. First, no dining solution using /spl diams/P achieves locality 0. Second, /spl diams/P is the weakest failure detector in the Chandra-Toueg hierarchy to realize locality 1.
- Publisher: IEEE Xplore
- Link to copy of this pubilcation on file with the publisher:
ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1281564
Download this publication:
- Citation:
Nigamanth Sridhar, Scott M. Pike, and Bruce W. Weide,
"Dynamic Module Replacement in Distributed Protocols"
in Proceedings of ICDCS 2003,
pp. 620-627. © IEEE 2003.
- Abstract:
Dynamic module replacement - the ability to hot swap a component's implementation at runtime - is fundamental to supporting evolutionary change in long-lived and highly-available systems. Most existing solutions require special-purpose middleware or depend on research languages with limited support for mainstream software development. We present a language-neutral technique for dynamic module replacement using Service Facilities (Serfs) - a pattern-based design strategy for decoupling runtime dependencies. We demonstrate the sufficiency of Serfs with respect to a litmus test of criteria for module replacement. Next, we extend the traditional scope of module replacement to encompass the domain of modules for distributed protocols. We conclude by applying the Serf strategy to illustrate dynamic replacement of mutual exclusion protocols in modules for distributed resource allocation.
- Publisher: IEEE Xplore
- Link to copy of this pubilcation on file with the publisher:
ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1203513
Download this publication:
- Citation:
Scott M. Pike,
"Encapsulating Concurrency with Early-Reply"
in Companion Proceedings of the 17th ACM Conference on Object-Oriented Programming, Languages, Systems, and Applications OOPSLA 2002,
pp. 18-19.
- Abstract:
Component methods often produce their final parameter values long before the method body is ready to terminate. To minimize client blocking, Early-Reply can be used to forward invocation results to the caller as soon as they are (safely) available. After executing Early-Reply, the method remainder and the client caller can proceed concurrently, modulo synchronization constraints. The prime motivation for Early-Reply, then, is to improve performance factors such as response time and resource utilization.Early-Reply received previous attention as a construct for explicit concurrent programming. It's value for sequential programming, however, has not been widely recognized. The present research supplies a formal treatment of Early-Reply as a basis for concurrent execution of sequential programs. In particular, we reformulate Early-Reply under local proof obligations that encapsulate concurrency as a (temporal) unit of information hiding. The upshot is that software developers can use Early-Reply to exploit the performance benefits of concurrent execution, without compromising the reasoning benefits of sequential programming.
- Publisher: ACM
- Link to copy of this pubilcation on file with the publisher:
doi.acm.org/10.1145/985072.985082
Download this publication:
- Citation:
Scott M. Pike and Nigamanth Sridhar,
"Early-Reply Components: Concurrent Execution with Sequential Reasoning"
in Proceedings of ICSR7.
Software Reuse: Methods, Techniques, and Tools. LNCS 2319, pp. 46-61. © Springer-Verlag 2002.
- Abstract:
This book constitutes the refereed proceedings of the 7th International Conference on Software Reuse, ICSR-7, held in Austin, Texas, USA, in April 2002.
The 22 revised full papers presented together with summaries or abstracts of keynotes, workshops, and tutorials were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on implementation, product lines, managerial and economic issues, generators, reuse of non-code artifacts, and design issues. The book contributes to bridging the gap between industrial practice and academic research and development in the area.
- Publisher: Springer
- Link to copy of this pubilcation on file with the publisher:
www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-2209833-0,00.html?referer=www.springer.de%2
Download this publication:
- Citation:
M. Sitaraman, S. Atkinson, G. Kulczycki, B.W. Weide, T.J. Long, P. Bucci, W.D. Heym, S.M. Pike, J.E. Hollingsworth,
"Reasoning About Software-Component Behavior"
in Proceedings of ICSR6 Software Reuse: Advances in Software Reusability.
LNCS 1844, 266-283. © Springer-Verlag 2000.
Citations:
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
- Abstract:
Mathematical modeling is essential for reasoning about component-based software. Without precise descriptions based on mathematical models, the potential benefits of component-based software development are unlikely to be fully realized because clients who use existing components will be unable to understand those components well enough to reason soundly about non-trivial programs which use them.
- Publisher: Springer
- Link to copy of this pubilcation on file with the publisher:
springerlink.metapress.com/(2o4yo455mjahlx55xv5uqo45)/app/home/issue.asp?referrer=parent&back
Download this publication:
- Citation:
Paolo A.G. Sivilotti, Scott M. Pike, and Nigamanth Sridhar,
"A New Distributed Resource-Allocation Algorithm with Optimal Failure Locality."
in Proceedings of PDCS 2000, Vol 2, pp. 524-529, IASTED/ACTA Press, 2000.
Citations:
[1]
[2]
[3]
[4]
- Abstract:
Failure locality measures an algorithm's robustness to process
failures. We present a new algorithm for the dining philosophers
problem | a classic problem in distributed resource allocation | that
has optimal failure locality. As a re nement, the algorithm can be
easily parameterized by a simple failure model to achieve
super-optimal failure locality in the average case. Keywords:
distributed algorithms, fault tolerance, dining philosophers, failure
locality. 1 Introduction The dining philosophers problem is a classic
and fundamental resource allocation problem [6]. Although rst
formulated as a shared-memory concurrency problem, it has since
received considerable attention as a distributed conict-resolution
problem [8]. It can be seen as a generalization of the mutual
exclusion problem, in which neighboring processes cannot access a
shared resource simultaneously. It has many applications in the
construction of other distributed resourceallocation algorithms,
including drinking p...
- Publisher: ACTA
- Link to copy of this pubilcation on file with the publisher:
www.actapress.com/proceedings/pdcs.htm
Download this publication:
- Citation:
Scott M. Pike, Bruce W. Weide, and Joseph E. Hollingsworth,
"Checkmate: Cornering C++ Dynamic Memory Errors With Checked Pointers."
in Proceedings of SIGCSE 2000, pp. 352-356. © ACM Press 2000.
Citations:
[1]
[2]
[3]
[4]
[5]
[6]
- Abstract:
Pointer errors are stumbling blocks for student and veteran programmers alike. Although languages such as Java use references to protect programmers from pointer pitfalls, the use of garbage collection dictates that languages like C++ will still be used for real-time mission-critical applications. Pointers will stay in the classroom as long as they're used in industry, so as educators, we must find better ways to teach them. This paper presents checked pointers, a simple wrapper for C++ pointers that prevents pointer arithmetic and other common sources of pointer errors, and detects all dereferencing and deallocation errors, including memory leaks. The syntax of checked pointers is highly faithful to raw C++ pointers, but provides run-time error detection and debugging information. After debugging, changing one #include is all that is required to substitute a non-checking implementation that is as fast as raw C++.
- Publisher: ACM
- Link to copy of this pubilcation on file with the publisher:
portal.acm.org/citation.cfm?doid=330908.331884
Download this publication:
Book Chapters
- Abstract:
This thesis describes theoretical and practical contributions to isolating partial failures in distributed systems to small, local neighborhoods of impact. Specifically, we develop scalable techniques for minimizing the impact of crash faults in a broad class of static resource allocation problems. Our particular lens of investigation focuses on the generalized dining philosophers problem as a fundamental abstraction for distributed resource allocation. Within this domain of inquiry, we construct fault-tolerant algorithms that restrict the scope of failures precipitated by crash faults. Additionally, we prove impossibility results for our techniques and optimality results for our constructions under different models of mutual exclusion and process synchronization. An overarching theme of our work is the central role of locality (and the limitations imposed by local knowledge) in the construction of scalable algorithms supporting the survivability and availability of distributed systems from a global perspective.
- Publisher: ETD
- Link to copy of this pubilcation on file with the publisher:
www.ohiolink.edu/etd/view.cgi?osu1092857584
Download this publication:
- Citation:
David S. Gibson, Bruce W. Weide, Scott M. Pike, Stephen H. Edwards,
"Toward a Normative Theory for Component-Based System Design and Analysis." in Foundations of Component-Based Systems, G.T. Leavens and M. Sitaraman, eds., Cambridge University Press, 2000, pp. 211-230.Citations:
[1]
Workshop Papers
- Abstract:
We extend traditional techniques for sequential specifcation
and verifcation to systems involving intrinsically concurrent
activities. Our approach uses careful design of component
specifcations to encapsulate inherent concurrency, and
hence isolate clients from associated verifcation concerns.
The approach has three parts: (i) relational specifcations to
capture the interleaved effects of concurrent threads of execution,
(ii) intermediate components to support a client's
view of being the only active thread of computation, and
(iii) a new specifcation clause to express requirements on a
client's future behavior. We illustrate these ideas, and discuss
their merits, in the context of a case study specifed
using RESOLVE.
- Publisher: ACM
- Link to copy of this pubilcation on file with the publisher:
Download this publication:
- Citation:
Bruce W. Weide, Scott M. Pike, and Wayne D. Heym,
"Why Swapping?"
in Proceedings of the RESOLVE Workshop 2002, pp. 72-79.
Citations:
[1]
[2]
[3]
[4]
- Abstract:
An analysis of the pros and cons of all options available for the built-in data movement operator in imperative languages shows that the swap operator is the best choice, while the assignment operator is the worst.
- Publisher: None
- Link to copy of this pubilcation on file with the publisher:
Download this publication:
- Abstract:
Software developers are eager to increase the scale of their
software products at a rate proportional to the growth of
computing resources. With memory, bandwidth, and computing
power doubling roughly every eighteen months, development
approaches that are not based on compositional
reasoning techniques can not be used to engineer the systems
of tomorrow. The enormous scale of these projects
far outstrips our ability to understand them using ad-hoc
approaches.
Industry best practice recognizes the importance of component
reuse, but the emphasis is weighted heavily on the
reuse of component code, often times neglecting the need
to reuse the effort that went into understanding the component's
behavior. That is, any scalable software engineering
discipline must provide mechanisms for reusing software
components, as well as mechanisms for reusing the reasoning
effort required to use those components.
This paper examines the Iterator pattern with regard to
compositional reasoning. The approach, touted as industry
best practice, is shown to provide ample opportunity
for breaking the principles of encapsulation. These various
hazards are briefly described, and several techniques for ensuring
safe use of the pattern are explored.
- Publisher: None
- Link to copy of this pubilcation on file with the publisher:
Download this publication:
- Abstract:
The explosive growth in hardware performance over the last 50 years has buttressed a belief in Moore’s Law that storage, bandwidth, and computing power will double approximately every 18 months. This unparalleled rate of progess in hardware technology has fueled an ever-growing industry of software applications. Unfortunately, the scale of current software has outpaced the development of tools and technologies for bringing software complexity within the tractable range of our limited human intellect. Research in separation of concerns has addressed this problem on many fronts, but it stands in need of challenge problems to motivate and evaluate new and existing approaches. This position paper outlines a formidable set of cross-cutting concerns pertaining to binary trees. The centrality of this data structure in diverse and conflicting application domains makes it an ideal challenge problem for current research.
- Publisher: None
- Link to copy of this pubilcation on file with the publisher:
www.research.ibm.com/hyperspace/workshops/icse2001/papers-index.htm
Download this publication:
Total Number of Publications: 13
publication admin
