Recommended books for professional computer scientists and software engineers...

By category...      

Design Methods for Reactive Systems

posted Oct 8, 2011, 10:07 AM by Fernando Berzal   [ updated Oct 8, 2011, 10:49 AM ]

Yourdon, Statemate, and the UML 

The application of well-known specification techniques to reactive systems is the focus of this book. A reactive system is "a system that, when switched on, is able to create desirable effects in its environment by responding to events." This perspective is not restricted to classical control systems (called directive systems in the book), but is also useful in a broader spectrum of information systems. In fact, this book's approach fits event-driven programming environments perfectly. Such environments are commonly used to develop modern graphical user interfaces.

While traditional transformation systems manifest a predetermined stateless behavior, and analysis of these is focused on how inputs are deterministically transformed into outputs, reactive systems are state-based, and exhibit a dynamic stimulus-response behavior. Basically, the reactive system under development (SUD) interacts with its environment by exchanging messages. Events in the environment arrive as stimuli to the SUD, and system responses are converted into actions in the environment. One of the recurring themes in the book, which is highlighted by the system engineering argument, is the importance of the environment. The argument states that the assumptions about the environment, plus the design specification, determine the properties of the resulting system, once the SUD is introduced. As a consequence, Wieringa advocates a more thorough environment specification than is usually done.

Wieringa focuses on specification techniques, describing their notations, explaining their semantic details, and offering some guidelines for their correct use. These techniques are arranged into four groups:
  • Function notations are useful for reaching an agreement with the customer, and are, therefore, best written in the customer's language (plain English). 

  • Entity notations describe the subject domain, and are entity-relationship diagrams, complemented by a dictionary of key terms. 

  • Behavior notations focus on the transformation of stimuli into responses, with accompanying state changes in the SUD. 

  • Communication notations are focused on the information exchange between systems, and complement the view offered by behavior notations. 

Once these types of notations are thoroughly surveyed, Wieringa wraps up the discussion of specification techniques with a chapter devoted to requirements-level system architectures, similar in spirit to the Object Management Group's model-driven architecture approach.

In the final part of the book, three different specification methodologies are described to illustrate how they combine different notations. Those methodologies are postmodern structured analysis (a Yourdon-style variant of structured analysis), Harel et al.'s Statemate, and a subset of the unified modeling language (UML), where the author introduces communication diagrams to ensure coherence between static structure diagrams (object and class diagrams) and behavior descriptions (statecharts).

Finally, in the last chapter, Wieringa presents "not yet another method" (NYAM), "the gist of existing methods," where he acknowledges that there is no silver bullet, and no single recipe for all specification problems. In fact, not all notations need to be used for all systems. The proper choice depends on the SUD functionality, and the notation's intended use (from informal prototypes to formal model checking).

In short, the author does his best to cover a wide range of specification techniques, and offers valuable insight into their underpinnings, complementing his discussions with case studies, exercises, and an uncommonly well-written glossary. The origins and rationale behind some of Wieringa's ideas can be found in the bibliographic remarks, along with some gems in the bibliography that deserve further reading.

The major shortcoming I found in this book was in its deviation from terminology and notation standards. For example, the author dismisses common terms, such as use cases or nonfunctional requirements, because of their possible connotations. In the first case, he prefers to use the term "service," although his focus on delivered value is akin to Constantine's essential use cases [1]. With respect to nonfunctional requirements, which have "the connotation that whether this property is present cannot be objectively decided" (p. 44), Wieringa misses the opportunity to use the goal analysis technique, which Gilb advocates [2], and about which it is clearly stated in this book that "all critical attributes can be specified in measurable testable terms."

Wieringa introduces his own share of new notations and variants (even the overly complex UML is somewhat expanded). We do not need more new models and notations, however; we certainly need better tools, and more practitioners to effectively apply known techniques [3]. With regard to this need, Wieringa's book is of value for practitioners, and food for thought for thinkers in general, and researchers in particular. If you want to fully understand the details of, and parallelisms between, specification notations, Wieringa is one of the best places to start.

-- Fernando Berzal, ACM Computing Reviews, 2003


[1] Constantine, L.L.; Lockwood, L.A.D.: Software for Use: A practical guide to the models and methods of usage-centered design (1st ed.). ACM Press/Addison-Wesley Publishing Co., New York, NY, 1999.

[2] Gilb, T.: Principles of Software Engineering Management. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988.

[3] Wiegers, K.: Read my lips: No new models!. IEEE Software 15, 5(1998), 10-–13.

Great Software Debates

posted Oct 8, 2011, 9:57 AM by Fernando Berzal   [ updated Oct 8, 2011, 10:27 AM ]

Davis has collected an interesting set of his previous essays on relevant issues for the software practitioner. He has appended a few questions at the end of each essay. That is all there is about actual debates in this book. The questions might stir debates in a classroom setting, or simply make you position yourself from a different point of view. This collection of essays is worth a look.

Funnily, a recurring theme in some essays is the use (and abuse) of software tools and techniques. The software development community has lived through many "silver bullets," which tend to be temporary fads. Oversold techniques are often easy to follow and misuse, because if they fail, they can be blamed, and our own egos are therefore protected. Unfortunately, that makes us look like lemmings (one of Davis' landmark essays). Throughout the book, you will be reminded that there are proven techniques that work, and produce moderate gains. Even "silver bullets" are good when properly used, obviously.

Management topics are covered in a whole section of the book. The author, a manager himself, describes the hard knocks that rookie managers suffer, and their most common mistakes, and even notes that a good manager has to disobey orders sometimes. As an entrepreneur, the author shares the lessons he learned at his own startup, as well as Ed Bersoff's lessons learned at BTG, providing an invaluable retrospective for those who aim to create a new company.

Another section of the book addresses requirements, one of the author's pet topics. He makes it clear that requirements have to do with understanding, not just with documentation. Requirements describe the external view of a system (namely, its phenotype), hence its object-oriented analysis limitations, as detailed in one of the essays. Some of the other essays in this section provide a good overview of the complete analysis phase, emphasizing requirements elicitation, triage, and volatility (as well as its inherent impact on estimation).

As someone who has worked in the industry, and also at universities, the author devotes another set of essays to technology transfer. The gap between researchers and practitioners is discussed, a gap that, surprisingly, exists in requirements engineering, where engineers are supposed to be able to understand their users' needs. As any good analyst would do, the author dissects the academic system, and highlights the severe limitations of the current educational model, where instructors usually don't have real-life experience in the topics they are supposed to teach, and incentives usually interfere with the ability to obtain practical research results.

Some personal recollections from the author complete the miscellaneous set of essays in the book. Since it could not be any other way, the perennial question about software development as an art or as engineering also crops up; a funny essay written by Jim Sanders highlights the parallels between writing music and writing software.

Even though most of the essays in this book are not new, they are as relevant today as they were when they were originally published. Two-thirds of the essays in this book will be familiar to IEEE Software readers, because they are rehashed from this bimonthly magazine (this fact should come as no surprise, since Davis is the former editor in chief). Despite this apparent lack of novelty, the topics covered by these essays deserve to be revisited with the benefit of hindsight, given that the current situation is not much different from what it was a few years ago. Moreover, the few essays that haven't been published before, and those that are harder to find, are valuable; they round off this excellent book.

This book deserves a place on any software engineer's bookshelf, next to Glass' book [1]. Like that book, this one will "make you think about the things you might have been taking for granted." At least, it will make you keep your brain in gear, an essential quality for software engineers settled into their daily routines.

If you think you are already acquainted with Davis' recommendations, let his common sense and sagacity become widely known and passed on. Get a copy of this book for your manager if you are a developer, for your boss if you are a manager, or for your partners if you are an entrepreneur. I did.

-- Fernando Berzal, ACM Computing Reviews, 2005


[1] Robert L. Glass: Facts and Fallacies of Software Engineering. Addison-Wesley Professional, Boston, MA, 2002. 


Applying UML and Patterns

posted Oct 8, 2011, 9:55 AM by Fernando Berzal   [ updated Oct 8, 2011, 10:49 AM ]

An introduction to object-oriented analysis and design and iterative development 

Software development books tend to focus on the details of the particular techniques they address, which makes it easy to forget the big picture. Typical books address each topic as if it belonged to a separate world. This book, in contrast, demonstrates how many different techniques and practices nicely fit together in the software development process.

This book is outstanding because of its peculiar organization. The book unfolds as an actual software project (two parallel projects, actually). The two case studies weave together the concepts covered, which are introduced at the points of the projects when they are most useful, lowering the learning curve. From a pedagogical point of view, the recurring use of the same case studies throughout the book is much better than devising unrelated examples for each topic covered (in spite of the typical, well-understood, fairly unimaginative, and, to some extent, boring point of sale (POS) system). Even though you may find this technique repetitious at times, since it often returns to the same underlying concepts to reinforce explained ideas, every experienced instructor uses this basic teaching technique. In any case, the projects follow an iterative process, so the book just reflects what actually happens in practice.

With respect to the book's contents, Larman demystifies the unified process. He focuses on its inception and elaboration phases, where most of the analysis and design work is done. Even though the book title focuses on unified modeling language (UML) and patterns, the books goes far beyond the use of UML diagrams to communicate ideas, and Gang of Four (GoF) [1] design patterns to codify design best practices. Fortunately, the misleading title may attract the people who can benefit most from the contents of the book, namely, those developers who want to expand their development skills. Larman also addresses analysis techniques, such as use case modeling [2], which are wrongly identified as "object-oriented analysis," when there is nothing object-oriented about them [3]. It is a stretch these days to talk about "object-oriented analysis."

The book mainly focuses on object-oriented design and its underlying principles, which are presented as "general responsibility assignment software principles." These are no more than general heuristics on how responsibilities should be assigned to software classes. Their discussion is noteworthy, but is also harder to understand for novice designers, because it requires a higher abstraction capability, a priceless ability for any self-respecting practitioner. Larman does a great job of introducing basic concepts and patterns, while demonstrating how to use UML to our advantage.

Apart from its in-depth coverage of object-oriented design, the book also presents other techniques that are useful in software development. These include the functionality-usability-reliability-performance-supportability (FURPS+) requirements categorization system; use cases, à la Cockburn; and the application of design by contract ideas, during the early phases of the project, by means of operation contracts. Larman also covers layered architectures, package design guidelines, and the N+1 view model for describing "the big ideas of the system." Some readers may feel that their pet techniques deserve a more in-depth treatment, which is virtually impossible if we take into account the broad scope of the book. For those interested in the details, Larman provides pointers to more information.

In summary, this is probably the best book I have seen on object-oriented design at the introductory level. Although it requires previous object-oriented programming knowledge (preferably in Java), it is easy to follow. The book is an ideal choice for self-learning, because it provides insight beyond the "how" of techniques, and explains the "why" behind them. Use it as a starting point, before attempting to fully understand more expert-oriented titles, if you are relatively new to object orientation. Use it as a refresher, to see how everything fits together, if you are more experienced.

-- Fernando Berzal, ACM Computing Reviews, 2005


[1] Gamma, E.; Helm, R.; Johnson, R.; Vlissides, J.: Design Patterns. Addison-Wesley, Boston, MA, 1995. 

[2] Cockburn, A.: Writing Effective Use Cases. Addison-Wesley, Boston, MA, 2001.

[3] Davis, A.M.: Great Software Debates. IEEE Computer Society, Los Alamitos, CA, 2004. 

Facts and Fallacies of Software Engineering

posted Oct 8, 2011, 9:49 AM by Fernando Berzal   [ updated Oct 8, 2011, 10:50 AM ]

Fundamental and Frequently Forgotten 

As Robert L. Glass points out in his introduction, and his book title suggests, this book is built around "a laundry list of facts and fallacies about building software". But there is something special in that laundry list: it tries to collect what we ought to know about software development but we frequently forget to remember, as well as some beliefs we give for granted although they are, at least, misleading (just plain wrong for Mr. Glass).

Given its topic, it is not surprising that the book original title was "Fifty-Five Frequently Forgotten Fundamental Facts (and a Few Fallacies) about Software Engineering", alias the F-Book. Somehow, the book title was shortened for marketing reasons and it lost the emphasis it put on the importance of the topics discussed.

The book is clearly written and easy to read, full of wisdom and with some doses of wit, just as the columns "Bob" Glass periodically writes for Communications of the ACM and IEEE Software. Moreover, the facts it examines are essential to software development activities and, although their references might change, their fundamentals will never be outdated. That makes this book a great book in comparison to the myriad of computer books which are written about the hottest topic of the day and whose relevance will not last much longer than trade magazines.

The facts and fallacies in this book cover the whole software life cycle, although several underlying themes recur throughout the book, such as the inherent complexity of software development (remember that software systems are probably the most complex systems ever built by humans) and the irrational hype which plagues our field (as exemplified by one-size-fit-alls advocates).

While you will find some classic facts such as "Adding people to a late project makes it later", as well as discussions of poor estimation and unstable requirements as the most common causes of project failure, you will also find some shocking facts and all of them will give you food for thought. Here is a sample of what I found particularly enlightening:

  • Since estimates are so faulty, there is little reason to be concerned when software projects do not meet estimated targets. But everyone is concerned anyway (Fact 12).
  • The answer to a feasibility study is almost always "yes" (Fact 14).
  • Eighty percent of software work is intellectual. A fair amount of it is creative. Little of it is clerical (Fact 22).
  • Missing requirements are the hardest requirements errors to correct (Fact 25).
  • One hundred percent [test] coverage is still far from enough (Fact 33).
  • Better methods lead to more maintenance, not less (Fact 45), since "enhancements represent roughly 60 percent of maintenance costs" (Fact 42).

Apart from the 55 facts which are dissected in the first part of the book, the author has chosen ten common misunderstandings in software engineering. These fallacies include pearls such as "given enough eyeballs, all bugs are shallow" (Fallacy 8), "the way to predict future maintenance costs and to make product replacement decisions is to look at past cost data" (Fallacy 9), and "to estimate cost and schedule, first estimate lines of code" (Fallacy 6). You will probably find yourself nodding as you read this part of the book and you will probably get shocked by some of the ideas you will find in this entertaining book, if not merely disturbed or plainly annoyed.

Why don't we learn to read program before we try to learn how to write them? That's the usual way we would learn a new language. Moreover, "60 percent of software's dollar is spent on maintenance, and 60 percent of that maintenance is enhancement" (the 60/60 rule) and "understanding the existing product consumes roughly 30 percent of the total maintenance time."

Some people might the book style somewhat irritating, since its contents are presented as more or less independent sections. Those sections collect Glass' wisdom in snippets which include a discussion of a particular fact, the controversy surrounding the fact, and some pointers to further reading. Although academics might prefer an alphabetical listing of hundreds of references, I have particularly enjoyed the short annotated bibliographic entries which are scattered throughout the book, in spite of the duplications which unavoidably appear when a particular reference is cited in several places. Somehow, almost every classic reference has its place in the F-Book.

This book is an invaluable resource for those people preparing to be software engineers in the future and also for those practitioners which want to refresh what they ought to know or just to reinforce what they believe in spite of existing controversies (mostly from "hypesters"). Since the book covers topics which are usually controversial, this book will also give you arguments for the next time you will find yourself trying to refrain your team of doing things the wrong way. If you love software development, you'll love this book. Enjoy it!  

-- Fernando Berzal, Dr. Dobb's Journal ERCB, 2003

Programming on Purpose: Essays on Software Design

posted Oct 8, 2011, 9:40 AM by Fernando Berzal   [ updated Oct 8, 2011, 10:32 AM ]

Why is software design so hard? Maybe because there aren't any guidelines for developing successful working systems. And although many design methods have been proposed, most too often teach us nothing more than their proponents' methodology and not how to make the best use of them.

Most classical analysis and design books fall short of telling us when to use the methods and techniques they advocate. Since there are no silver bullets (that is, no "one-size-fits-all" method in software engineering) and, as P.J. Plauger says in Programming on Purpose: Essays on Programming Design, "we often cannot articulate why we do what we do when we do it," our experience ends up being the only guide we have when facing new projects. This leads many software projects to failure, rather than repeatable successes.

The patterns movement has filled a niche by cataloging well-crafted solutions to many analysis and design problems (see, for example, Erich Gamma et al.'s Design Patterns: Elements of Reusable Object-Oriented Software or Martin Fowler's Analysis Patterns: Reusable Object Models). But even before the patterns fad, P.J. Plauger disseminated simple but powerful ideas in dozens of magazine articles and a column, mainly in late Computer Language magazine. In some sense, Programming on Purpose complements the pattern approach because patterns are usually employed to describe solutions at the architectural level, while the principles Plauger describes are focused on detailed design and coding.

Programming on Purpose is the keystone of a three-volume collection of essays he wrote between 1986 and 1993. This volume focuses on software design while the others collect articles on people and technology. In spite of its somewhat dated context (part of it was written before the widespread use of object-oriented techniques, WIMP interfaces, and other prevailing practices), the ideas and principles in this book are surprisingly fresh. In fact, Plauger's observations are timeless and will be always relevant to software professionals because they tackle the problem of mastering complexity that lies at the heart of software development.

Programming on Purpose presents excellent discussions on a wide range of design methods and techniques, from the stepwise refinement used in top-down design to the use of grammars to parse input data (left-to-right design) or a structure approach to build programs that model the structure of the output data (right-to-left design). A total of 12 design methods are presented, along with their strengths and weaknesses. Although Plauger's design methods categorization technique is somewhat artificial, the book's value is in no way diluted since all methods are put into a context of guiding you using analogies and advice.

Apart from his survey of software design methods, Plauger provides some interesting nuggets such as three essays on demystifying object-oriented programming (a novel trend when the essays were written), some ideas on software development that could seem to be counterintuitive ("software design heresies," as Plauger calls them), and a curious approach to teaching software engineering that could be an eye-opener for many instructors.

A couple of chapters with interesting references to further reading and Plauger's view on landmark software design publications complete this superb book. Programming on Purpose is a must have book for anyone involved in professional software development. 

-- Fernando Berzal, Dr. Dobb's Journal ERCB, 2002

Design Patterns: Elements of Reusable Object-Oriented Software

posted Oct 8, 2011, 9:30 AM by Fernando Berzal   [ updated Oct 8, 2011, 10:48 AM ]

A new language... for talking about proper designs 

In software development, reuse is The Holy Grail. Reusing existing software artifacts is the most cost-effective way to reduce development time and effort. But code snippets and finished software components are not the only artifacts which can be reused. I am sure you already reuse your prior development experience when facing new challenges. This book is just about that. The Gang of Four (GoF) - as the authors are popularly known - try to record experience in object-oriented design to help developers improve their programming skills. As the book preface says...

This book isn't an introduction to object-oriented technology or design. Many books already do a good job of that. This book... describes simple and elegant solutions to specific problems in object-oriented software design. ... Once you understand the design patterns and have had an "Aha!" (and not just a "Huh?") experience with them, you won't ever think about object-oriented design in the same way. Design patterns try to capture common design problems and then they study different solutions and analyze their trade-offs. Their purpose is to document good designs that solve problems you will certainly find in almost any serious software development project.

As other software development best practices, design patterns help us develop more flexible and maintainable software through the use of well-designed interfaces which encapsulate particular implementations. This book proposes a modular approach which encourages the use of object composition and delegation over class inheritance in order to reduce coupling among classes.

The GoF's book is an essential catalog of object-oriented design templates. Each template or pattern can be used as a starting point to develop new object-oriented software, and also in the process of refactoring (i.e. reorganizing and redesigning) existing software systems. Each pattern in this book abstracts key issues of common design structures, is analyzed in depth and is labeled with a short name in order to facilitate communication among developers. Pattern names broaden our technical vocabulary and make easier for us to discuss possible solutions and their trade-offs.

This book discusses each design pattern in self-contained chapters. Each chapter labels the design pattern, presents the problem it intends to solve, describes its solution, and addresses the consequences which could derive from the use of the design pattern in real systems. Some code snippets (in C++ and Smalltalk) illustrate the inner details of each pattern and references to known uses of each pattern are also included, although you will find that you have probably used most patterns in your best projects.

As stated above, patterns are studied separately, although they are organized into three main categories:

  • Creational patterns make a system independent of how its objects are created, composed, and represented (e.g. object factories).
  • Structural patterns present ways to organize objects: how classes and objects are composed to form larger structures (e.g. wrappers, composites, and proxies).
  • Last, but nor least, behavioral patterns are concerned with the assignment of responsibilities among objects (e.g. chains of responsibility, publisher/subscribers, etc.).

The book organization, its quick index, and its diagrammatic roadmaps make it a worthwhile reference to keep at hand on your favorite shelf. This -now famous- book is the flagship publication of a growing community whose interest in well-designed software complements the traditionally academic focus on software development techniques and methodologies. Methodologies teach us how to solve development projects, design patterns show us elegant solutions to those problems.

Once this book is read, and probably re-read, it acts as a real eye-opener. As the authors claim, you will never see your designs in the same way. Design patterns are here to stay. Stay tuned!

P.S.: Many of the design patterns which are described in this book are now part of the mainstream programming culture, so you will probably find many design patterns you are already aware of.

-- Fernando Berzal, Dr. Dobb's Journal ERCB, 2002

The Quest for Artificial Intelligence

posted Oct 1, 2011, 3:23 AM by Fernando Berzal   [ updated Oct 1, 2011, 8:34 AM ]

The history of ideas deals with the proposal, rebuttal, and evolution of ideas over time. This is always a fascinating topic, as it makes us aware of many of our underlying assumptions, suggests alternatives we might not have considered, and makes us reflect upon the trends and controversies that shape the history of a research field. The field of artificial intelligence (AI) is particularly relevant, due to the multitude of distinct ideas that have been devised, borrowed from other fields, adapted, combined, and often discarded, but also adopted to build many practical systems now in use. Now that the field has been with us for the last 50 years or so, we are offered the opportunity to read a roughly chronological account of its evolution, from the perspective of one of its pioneers.

Nilsson considers intelligence to be “that quality that enables an entity to function appropriately and with foresight in its environment.” Throughout his historical account, he surveys many of the major milestones that have led AI to its current state, from the often-unsuccessful trials of people who were ahead of their time and its modest origins in related disciplines. Logic, statistics, philosophy, psychological theories, what we now call neuroscience, and engineering all contributed to the early experiments that led to the first AI systems built at sites such as Stanford University, the Massachusetts Institute of Technology (MIT), and Carnegie Mellon University (CMU), in the 1950s and 1960s.

Those early efforts led to robotic systems such as Shakey. Nilsson’s first-hand recollection of it is certainly enjoyable. At its time, Shakey was “the first robot system having the abilities to plan, reason, and learn; to perceive its environment using vision...[;] and to monitor the execution of its plans.” Many ideas now familiar to computer scientists, such as the A* heuristic search procedure or the STRIPS planner, were originally proposed by Nilsson and his collaborators during the late 1960s and the early 1970s. Many knowledge representation techniques, such as scripts and frames, are from the same period (semantic networks were proposed earlier).

During the following decade, research led to the development of many perceptual systems that allowed machines to interact more like humans. Some noteworthy computer vision algorithms and many natural language processing techniques fall within this category. Speech recognition systems, for instance, also introduced an assorted toolbox that would later be used in many other contexts, from hidden Markov models to blackboard architectures. Work on knowledge representation, on the other hand, led to the flourishing of expert systems during the 1980s, whose techniques are at the heart of modern business rules engines.

Significant success toward the goal of making a machine behave in ways that would be called intelligent if a human behaved so also led to overly optimistic predictions. This caused an expectations management problem that finally led to the “AI winter,” as Nilsson puts it. Apart from mentioning the funding and political issues that influenced the development of AI research projects, Nilsson complements his chronological account with a proper discussion of the “controversies that were simmering on the sidelines and within the field itself.”

Good-old-fashioned AI ultimately led to the development of new paradigms, whose growth led to the now-fragmented AI subfield, from machine learning and data mining, to knowledge engineering techniques, computer vision systems, and the statistical natural language processing techniques currently in vogue. We have already witnessed some extraordinary achievements, from world-champion-level game-playing machines, to autonomous robots and driverless automobiles. Nilsson comments on challenging problems that AI techniques have recently helped solve, and then goes on to predict what AI programs might still do. Even though he modestly acknowledges that “more accomplished historians ... have wisely avoided writing accounts that get too close to the present,” Nilsson is bold enough to predict and even advocate for the appearance of human-level AI during the current century.

Apart from the fact that one might find the final human-level AI issue too debatable to be included in a historical retrospective such as this, Nilsson provides an otherwise balanced look at what AI has been able to do during its first 50 years of existence. His personal recollections and the rationale behind many decisions, as retold by an insider, make this book a unique contribution, interesting both for the informed and for the general reader. Both kinds of readers can learn a lot from Nilsson’s book about the evolution of this now-mature research field. The book is written in a friendly conversational style, without any unnecessary mathematical formalisms, and is richly illustrated with many diagrams that depict representative AI systems and photographs of the many innovators that led to their development.

Reviewer:  Fernando BerzalReview #: CR137774 (1102-0149)

También disponible en

Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations

posted Oct 1, 2011, 3:13 AM by Fernando Berzal   [ updated Oct 1, 2011, 9:40 AM ]

Loosely defined, “multiagent systems are those systems that include multiple autonomous entities with either diverging information or diverging interests, or both.” Obviously, this definition is broad enough to cover a wide variety of real-world systems, from different kinds of complex networks to interactions among human individuals and organizations. In fact, many of the ideas discussed in this book apply to situations that have nothing to do with multiagent systems, commonly viewed as the modern approach to artificial intelligence (AI).

This thorough textbook on multiagent systems mainly focuses on game theory. Written from a computer scientist’s perspective, this book surveys many of the game-theoretic ideas that have been developed since the Second World War, when von Neumann and Morgenstern’s landmark book [1] created the interdisciplinary field of game theory. Game theory, as a branch of applied mathematics, is typically associated with economics and other social sciences. However, as the study of the interaction among independent agents, its strong connections to multiagent systems is self-evident, so a textbook on game theory from a computer scientist’s perspective is more than welcome.

Most of the book is devoted to game-theoretic concepts. Many chapters study competition among agents or noncooperative game theory, while coalitional game theory is addressed in a separate chapter. In these chapters, readers will find the most important topics in game theory, as well as the essential mathematics behind them and some detailed proofs. Apart from the mathematical proof that every game with a finite number of players and action profiles has at least one Nash equilibrium--a result that gave Nash a Nobel Prize in economics and was, let’s say, freely interpreted in the Hollywood blockbuster A Beautiful Mind--you will also find discussions on the computational complexity of computing solution concepts of normal-form and extensive-form games. A variety of other game representations are also reviewed.

Another group of chapters is devoted to “protocols for groups,” a term used by the authors to refer to social choice. From the designer’s perspective, these chapters analyze what rules should be put in place by the designer orchestrating a set of agents. These rules include voting schemes and ranking systems. Mechanism design, as “an exercise in incentive engineering,” is the strategic version of social choice theory. Its better-known application, auctions, also deserves its own chapter, since it is directly related to multiagent resource allocation.

A few chapters address other important topics in multiagent systems, from coordination and communication to learning. The coordination chapters deal with distributed problem solving, focusing on constraint satisfaction (for example, using asynchronous backtracking) and optimization (for example, distributed dynamic programming and learning real-time A*). The short communication chapter discusses when talk precedes action (cheap talk and speech-act theory) and when actions speak louder than words (that is, talking by doing--signaling games as games of asymmetric information). Finally, the chapter on multiagent learning also approaches the topic from a game-theoretic perspective, and is based on an AI paper written by Shoham and other collaborators [2].

The book ends with a couple of chapters on logical theories, which will interest those who work on multiagent systems, and a few short technical appendices. The chapters on logic explore modal logics and beyond. Modal logics qualify the truth of a judgment by means of unary modal operators. The authors also study how knowledge and belief statements change over time (belief dynamics) and how to formalize the notion of goals and intentions. The brief technical appendices provide quick refreshers on probability, linear/integer programming, Markov decision problems, and classical logic--subjects that are needed to understand the rest of the book.

The authors’ style is quite formal, since the textbook is mainly addressed to graduate students and researchers. Although Shoham and Leyton-Brown often refer to their chapters as crash courses, casual readers should not start their inroads into game theory by reading this book. Later, they can refer to this rigorous textbook, if they want to plow through the mathematical details.

Reviewer:  Fernando BerzalReview #: CR137285 (1008-0777)
1)von Neumann, J.; Morgenstern, O. Theory of games and economic behavior (60th anniv. ed.). Princeton University Press, Princeton, NJ, 2007.
2)Shoham, Y.; Powers, R.; Grenager, T. If multi-agent learning is the answer, what is the question?. Artificial Intelligence 171, 7(2007), 365–377.

También disponible en

Analyzing Social Media Networks with NodeXL: Insights from a Connected World

posted Oct 1, 2011, 3:01 AM by Fernando Berzal   [ updated Oct 1, 2011, 9:39 AM ]

For the last dozen years, networks have attracted the attention of many researchers and practitioners. Some simple network models [1,2] have achieved significant popularity beyond Andy Warhol’s 15 minutes of fame. Such models have spurred the development of a whole new field of research that combines graph theory, computer science, economics, and other social sciences. The generated momentum has led to the recent publication of some outstanding textbooks on networks [3,4,5].

More than a classical textbook, this book is a well-written educational handbook that describes how we can apply part of the so-called science of networks to the analysis of medium-size networks. The authors impose the size constraint because of the book’s reliance on visual inspection and interactive visualization techniques (sometimes referred to as visual analytics). Since the available space on a screen is severely limited, one cannot expect to analyze a billion-node network using the tool described in this book.

The book also provides a nice overview of the field of social media networks. (Social media corresponds to Web 2.0 technologies.)

A surprising feature of this book, especially when compared with its more formal counterparts, is that the authors avoid any kind of mathematical formalization of the topics they discuss. They seem to have followed Stephen Hawking’s advice: “Someone told me that each equation I included in the book would halve the sales” [6]. In fact, many readers will be grateful to learn that the authors do not include a single mathematical equation, not even to define important network metrics from an intuitive point of view. (Stephen Hawking did include a single equation: Einstein’s famous E=mc2.) However, some chapters include “Advanced Topics” sidebars that describe how to get the most out of Excel when using the NodeXL tool.

NodeXL is a social network analysis open-source plug-in for Excel 2007/2010. It lowers the barrier of entry that is typical of many other network analysis tools; anyone with some experience using spreadsheets can use it. NodeXL computes some of the best-known network metrics, and, with the help of some Excel features, makes network filtering and visualization a breeze. It also implements different network layout algorithms and clustering techniques to discover natural groups of nodes within a complex network. The book only mentions one clustering technique, but more alternatives are available by downloading the latest version of the software from the NodeXL homepage (

The introductory part of the book goes through some of the history and core concepts of social media and social network analysis, always with an eye to social network visualization and for a general audience--it omits technical details. Later, it proposes a framework for categorizing different collaboration technologies and describes 11 categories as examples.

The second part of the book features a variety of tool details. It presents an eight-hour tutorial that surveys NodeXL’s main features.

The bulk of the book, however, is the third part, which contains eight chapters on as many different case studies. These chapters, which are often by international researchers on social media, focus on different kinds of social networks and follow a more or less standard structure. They cover email, threaded communications, Twitter, Facebook, organizational World Wide Web (WWW) networks, Flickr, YouTube, and wikis.

The chapters describe the particularities of each technology and present information on the types of networks one can analyze, from Facebook ego networks to the interplay between content and community networks on Flickr or YouTube (that is, the content provided by tag clouds and video networks versus the structure provided by user networks, where you can explore each user’s followers and/or friends). Each chapter concludes with some observations for practitioners, an agenda for researchers, and a good selection of relevant bibliographic references for each case study. Ideally, these analyses should provide some useful insights and a good idea of what types of questions one can ask (and answer using social network analysis) about individuals, groups, temporal evolution, and structural patterns in social media networks.

In summary, Hansen, Shneiderman, and Smith, along with their collaborators, have written a readable introduction to the field of social media network analysis. Furthermore, the book is a nice tutorial on an interesting tool that readers can experiment with on their own. For example, the readers can simply use the Facebook application provided by Bernie Hogan, one of the book’s collaborators, to analyze the ego networks that they know best: their own network of friends, family, and acquaintances. This book offers a sure way to understand some of the basic concepts of network analysis.

Reviewer:  Fernando BerzalReview #: CR138913 (1111-1143)
1)Watts, D.J.; Strogatz, S.H. Collective dynamics of “small-world” networks. Nature393, 6684(1998), 440–442.
2)Barabási, A.-L.; Albert, R. Emergence of scaling in random networks. Science 286, 5439(1999), 509–512.
3)Newman, M.E.J. Networks: An Introduction. Oxford University Press, Oxford, UK, 2010.
4)Easley, D.; Kleinberg, J. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, New York, NY, 2010.
5)Jackson, M.O. Social and Economic Networks. Princeton University Press, Princeton, NJ, 2008.
6)Hawking, S.W. A brief history of time: from the big bang to black holes. Bantam Books, New York, NY, 1988.

También disponible en

Network Science: Theory and Applications

posted Oct 1, 2011, 2:50 AM by Fernando Berzal   [ updated Oct 8, 2011, 10:46 AM ]

Networks pervade our lives. As graphs representing interconnected systems, they can represent social interactions, economic relationships, power grids, computer networks, Web links, bibliographic citations, or biochemical processes. Whether the networks are social, economic, technological, or biological, their study has spurred a lot of interest over the past decade or so.

The Web established a market for many popular books on networks. Some of these have been entertaining and informative—for example, Duncan Watts's Six Degrees or Albert-Laszlo Barabasi's Linked. However, they aren’t rigorous enough for more demanding readers. Those wishing to plumb the depths of networks have had to make their way through countless research papers, which necessarily offer a fragmented view of any field. Even worse, network research terminology is often confusing, given the youth of this field and the different specialties contributing to it. Hence, Ted G. Lewis's textbook offering a panoramic view of this emerging research area is welcome.

The Mathematics Behind Network Models

According Lewis, network science reflects the combination of graph theory, control theory, and cross-discipline applications. Calling it a science, however, is probably an overstatement—the kind of hype that has made some people dismiss network research as a passing fad or fabrication, ignoring important lessons this field can teach us.

The subtitle might also be misleading. Lewis has written the book with graduate students in mind, so it's more theory than applications. This is partially justified because Lewis has tried to separate the wheat from the chaff to produce a valuable textbook. In this yet-to-mature field, theoretical models are the wheat while particular applications are usually the chaff. This is because new observations and a better understanding of the studied processes often make research results obsolete in a quite short period of time.

After some introductory material on the historical roots of networks and a brief overview of graph theory, Lewis analyzes some of the most popular network models that researchers have proposed to formulate hypotheses about observed phenomena. These range from Watts-Strogatz small worlds and Barabasi-Albert scale-free networks to flow, influence, and netgain networks.

Traditional graph theory has typically focused on network static properties, which Lewis also uses to study different network classes. However, modern network models focus on the dynamic behavior of interconnected systems. Lewis concentrates on four network properties:

  • emergence — the process whereby a macroscale (global) property emerges as a consequence of the repeated application of microscale (local) modifications.

  • epidemics — the propagation of a signal (for example, contagion) through a network.

  • synchrony/stability — the synchronization/stabilization of network nodes under changing conditions, which includes the study of conflicts and group consensus in influence networks, for example.

  • vulnerability — the potential impact of node and link failures (for example, in the power grid), as well as the protection of the stability in Kirchhoff (flow) networks.

The final chapters turn to economics and biology as promising application domains for network theory. Lewis posits that netgain networks might be useful models for investigating how economic markets behave, that while biological network models show promise as research tools.

Style pros and cons

Lewis has made an extraordinary effort to provide a first textbook in this fascinating field. However, being first also has some disadvantages. Apart from typos that might be unavoidable in a first edition, especially if publishers want to cut proofreading and editing costs, I found some explanations more convoluted than necessary, even misleading at times. For instance, when discussing a classical paper on the Web topology as a directed graph, Web links are mistaken for physical network connections. Web nodes—that is, Web pages—are incorrectly identified as "nodes that send messages such as email" (page 159). Fortunately, such glaring errors are few, but they're unsettling in any textbook because they raise some doubts about its overall rigor and thoroughness.

The text is generally clear, but somewhat wordy and repetitive. The book feels as if it's written from course notes. Some repetition is desirable and even necessary in oral presentation, but it isn't as welcome in written form. For instance, the detailed introductions to each chapter almost summarize all the material in the chapter itself, thus virtually removing any pleasant surprise you might find from delving into the details. I find detailed summaries more useful at the end of chapters, rather than the beginning.

Lewis concludes each chapter with some exercises as well as interesting issues—even open research questions—that are "left as an exercise to the reader." He provides some Java software tools that support the exercises. (He even discusses some code snippets in the text—something I thought often distracted from the main discussion.) The software tools are invaluable for readers to experiment on their own, because many network issues can only be resolved through computer simulations followed by some curve fitting. All in all, I would recommend Lewis's textbook for graduate students and professionals with a keen interest in network models. Those with a more general interest might start with the popular books, then proceed with this book for a more thorough study. Despite its theoretical slant, casual readers can easily skip the mathematics and still glean much from this book.

-- Fernando Berzal is a member of the IEEE Computer Society and a senior member of the ACM. Contact him at

[IEEE Software, August 2009]

También disponible en

1-10 of 14